[BMAX] Searching through a 2D array from any starting index.

[Pixel_Outlaw]

I don't know if this is a common practice but I would like to search through a 2d array completely starting at a random index.

If an index contains the value I need I return it quitting the search.


Currently I find all the values I want in the array put them into a list, then select a random one.

Why this is not good:

1. The entire array must be searched, all elements must be checked before adding them to the list.
2. A list must be created to hold elements for random selection later.
3. The list must be cleared and populated for each search.
4. This is a worst case scenario. ALL elements must be evaluated to find fitting values.


Why I would like to do searching a 2d array starting at a random position.

1. The first fitting element found may be returned and the search stopped it is already a randomly selected element because the search was started in a random index.
2. No overhead in creating and clearing the list.


Please help if you can. My program is running borderline unacceptably slow.

The array is measured in "length" and "height".

[Shockwave]

Hmm.

I can kind of see why you would want to do this, perhaps sorting the array into order at some point would mean that you could cut down on the amount of searching you need to do?

You could jump in at the point you wanted then.

[Jim]

With the information you've given, it's impossible to come up with any better solution.  If you know more about the data than you're telling us then it might be possible to improve the algorithm - ie. what makes a 2d point 'interesting' and how were the 2d points calculated.

Even in this case, you're just creating pointers to the things you want to pick from, not copying them, right?   Point 3 is utterly redundant if you do that.

Jim

[Pixel_Outlaw]

Well basically this is for my maze generator. (big surprise eh)

The array holds "cell" objects. The cells have 5 attributes, 4 walls (boolean) and one visited value.

The current algorithm needs to pick an RANDOM available unvisited cell that has a visited neighbor. The I do not wish to store nor check through 40000 possibilities scanned in from an array.

I have to learn a bit on pointers. I keep putting it on the back burner. My (programmer's) stove has about 16 of these back burners.

I need a randomly chosen cell that meets a criterion with the worst case scenario of having to search all elements.

[Pixel_Outlaw]

The algorithm I had in mind really put the rubber to the road. It ran MUCH MUCH faster that searching from the same index each time. I don't understand why it works but I just had a hunch.

feel free to compile. You can see documentation at the bottom of the file.


http://rafb.net/p/Y9N4Ho96.html

[zawran]

Nice work on the maze generation. Something like this could be useful for a dungeon crawl game. But it would need room sized areas here and there, and more than one way to get around the dungeon. But thats another topic all together. For what this does, it does it very effectively. Great work.

[Pixel_Outlaw]

I plan to use this for that actually.

Have a look at this link, it gives an algorithm to convert a maze to a dungeon with rooms.
http://www.aarg.net/~minam/dungeon.cgi

[zawran]

That is a very good link, and I will take a deeper look into his dungeon generation code. I have always had an interest in RPG generation software of any kind and have made a few item and name generators previously. But a good dungeon generation program is one of the things I have not done yet, but would like to. And as he states on his pages, there is a difference between mazes and dungeons, although related, so I am sure that I can learn something from him.