Recursive Flood Fill Function

You need a sorted list, and end list and a map.
In the map, you know which tiles are passable or not (you check to see if there the same tile/something else, i'm a little short on time).

Simple way

do until the list is emptyTake the node off the top of thie list, call it lFind all of the children of l, which can be traversedPush them onto the sorted list, remiving duplicates.Push them also onto the end listloop

At the end, the sorted list will be empty, and the end list will contain every node that is in the floodfill.

You can use a hash table if you want, or anything else, which allows you to quickly check for duplicates (o(1) or o (log2n) only. Everything else is just slow), the end list can be anything that you want, usually a sorted list.

Children of l - Nodes which can be moved to, if you were on l.

That should be it, pm if anything else is needed of me. Or you can post and get someone else to help.

From,
Nice coder

What is a hash table?

Ok i'm back again, for a few minutes.

Hash tables, are used to store data.
[google]
Please click on the google to begin your journey.

Basically you have your key and your data and your table.
To acess your data, you give the hash table your key and it finds your data.
Whats so good about this? the amount of time that it takes to find your data doesn't change if you have 10 records or 100billion.
How does it do this?

It turns your key into a number. Usually a really really large number.
That then it turned into an array index, by finding the remainder after dividing it by the hash table size. The data is then stored in the index.

Note: Hashtablesizes must be prime. It is complex to explain why, so just do it.

Now, your asking, what happens when two keys hashes are equal to the same thing (mod hashtablesize)? This is the main problem.

You can do a lot of things.

First, you can make the table bigger (obviously this is an ok situation, because primes are pretty close to each other. But only if you onoly have a few records, because you have to go through them all and copy them into the correct positions.)

Or you can do what is known as chaining.
What is chaining?
Google it.

I really don't use hash tables, i just use sorted lists. There easier to make, use maintain, and authough there not as fast for insertion/deleation there mighty fast for accesing (and some well-oiled sorted lists are faster then most hash functions.)

From,
Nice coder

Well Nice Coder, that's not too bad an answer from you.
What you described is in fact the iterative version of the floodfill algorithm.
One thing though, instead of a sorted list of possible tiles to fill, you could use a data structure which does not permit duplicates, such as a set. This handles duplicates for you.

You also missed the first step:

Place the seed (usually clicked-on) tile in the list.

A hash table is a method whereby every item is designated a certain locaion within an array, through some kind of mapping called a 'hash' function. The elements tend to randomly scattered throughout the array by the hash function, and are stored in no particular order. Duplicate items will always have the same hash position though. Occasionally by coincidence non-duplicate entries can also have the same hash position.

Anyway, for duplicate removal you hash all items and then check only the items that fall into each hash position to see if there are any duplicates. This means that you have to check each item against far fewer items, as most non-duplicate items would have a different hash position.
It is far better than checking each item against EVERY other item.

An actual recursive version of the algorithm can be found on this thread, though iterative versions of an algorithm are often faster.

[Edited by - iMalc on March 6, 2005 11:08:28 PM]

Quote:

Original post by Nice Coder Note: Hashtablesizes must be prime. It is complex to explain why, so just do it.

Hmm, we cross-posted.
WHAT, That's statement is ridiculous! There is no sensible reason I can think of to use a prime number as a hash-table size. Doing so would only cause poor performance. I would recommend always using a power of two for the table size - ALWAYS. Simply because you can simply 'and' the hash value with a bitmask to give the final position. If your table size is a power of two then your compiler might be able to do that for you, but I always do this (example, using a crc as the hash function):

const int HASKMASK = 0xFF;hashpos = crc(mydata, sizeof(mydata)) & HASHMASK;

Quote:

Original post by iMalc Quote: Original post by Nice Coder Note: Hashtablesizes must be prime. It is complex to explain why, so just do it. Hmm, we cross-posted. WHAT, That's statement is ridiculous! There is no sensible reason I can think of to use a prime number as a hash-table size. Doing so would only cause poor performance. I would recommend always using a power of two for the table size - ALWAYS. Simply because you can simply 'and' the hash value with a bitmask to give the final position. If your table size is a power of two then your compiler might be able to do that for you, but I always do this (example, using a crc as the hash function): const int HASKMASK = 0xFF;hashpos = crc(mydata, sizeof(mydata)) & HASHMASK;

Nonprime hashtables cause more collisions.
(it was in a few places here and there)

See my test results.
For n = 1000 to 10000
8928 Collisions for y = 101
9020 Collisions for y = 100
I'll post more tests later.

From,
Nice coder

I promise no efficiency...

Okay, I majorly overreacted, sorry. However, the liklihood of collisions should only be increased by using a prime number table size, if the hashing function is not very good at giving randomised hash values to begin with.
Using a CRC would typically give very good values.

It's true that sometimes simpler hashing algorithms are used (for speed reasons), however I believe that there is more advantage in having a good hashing function, than trying to make the fastest hashing function. Mod is as slow as divide, and possibly as slow as an entire crc function (depending on how the crc function is implemented). So the speed of the hashing function isn't necessarily the governing factor in the speed of the whole implementation.

Quote:

Original post by Mattman I promise no efficiency... *** Source Snippet Removed ***

Beware calling that with srcTile and destTile the same!

Quote:

Original post by iMalc WHAT, That's statement is ridiculous! There is no sensible reason I can think of to use a prime number as a hash-table size. Doing so would only cause poor performance. I would recommend always using a power of two for the table size - ALWAYS. Simply because you can simply 'and' the hash value with a bitmask to give the final position. If your table size is a power of two then your compiler might be able to do that for you, but I always do this (example, using a crc as the hash function): const int HASKMASK = 0xFF;hashpos = crc(mydata, sizeof(mydata)) & HASHMASK;

Good job, you just threw away the upper 24 bits of your hash function.

something like



I also promise no efficiency.

Oh yes - the above is iterative, not recursive. It will fill in a "diamond" formation.

Mark

Quote:

Original post by Nice Coder Nonprime hashtables cause more collisions. (it was in a few places here and there)

That is a pretty bad way of reducing collisions, you should really improve your hash algorithm if you get a statistically significant difference. Which your test doesn't: 92/~9000 is about 1% difference. Your margin of error is almost definitely larger than that.

Quote:

Original post by sjelkjd Quote: Original post by iMalc WHAT, That's statement is ridiculous! There is no sensible reason I can think of to use a prime number as a hash-table size. Doing so would only cause poor performance. I would recommend always using a power of two for the table size - ALWAYS. Simply because you can simply 'and' the hash value with a bitmask to give the final position. If your table size is a power of two then your compiler might be able to do that for you, but I always do this (example, using a crc as the hash function): const int HASKMASK = 0xFF;hashpos = crc(mydata, sizeof(mydata)) & HASHMASK; Good job, you just threw away the upper 24 bits of your hash function.

Which is exactly what you would want to do if your hash table has exactly 256 entries (as I thought most people would assume I meant, here). So what's your point?

Sorry for the little hijack.

How can one dynamically determine the correct prime number efficiently when you don't know the number of items that will be loaded in the hashtable? I know there are some algorithms out there to compute prime numbers, but those all aren't very fast due to the complexity involved.

Also I heard that hashtables should have storage for 33% extra which mostly keep empty, to keep collisions to a minimum, is that correct? If so, when should one enlarge the table to a new bigger prime?

SHort answer: Yes, but i don't use hashtables that much, so don't trust me on it.

Note: You need that empty space to keep chaining to a minimum. (chaining is slower then direct lookup by a rather largish amount).

From,
Nice coder

Quote:

Original post by jeroenb Sorry for the little hijack. How can one dynamically determine the correct prime number efficiently when you don't know the number of items that will be loaded in the hashtable? I know there are some algorithms out there to compute prime numbers, but those all aren't very fast due to the complexity involved. Also I heard that hashtables should have storage for 33% extra which mostly keep empty, to keep collisions to a minimum, is that correct? If so, when should one enlarge the table to a new bigger prime?

You definately want some spare space in there i.e. more slots than items. But at the same time it isn't so good to have say 10x more slots than items, because it causes unnecessary caching slowdowns. One third empty is probably optimal.

Don't worry about using a prime number for the size, so long as you have a good hash function, like CRC. I have found that a good enough size for a hash table is simply the next power of two greater than the number of items. Minus 1 for the mask, of course, which is so easy to calculate...

inline unsigned HashMaskForTableOfSize(unsigned x) {    x |= x >> 1;    x |= x >> 2;    x |= x >> 4;    x |= x >> 8;    x |= x >> 16;    return x;}

If your table grows a lot through the course of your program then you should double it when the number of items reaches the number of slots. It makes sense that you may as well use powers of two right from the start. btw if you grow by the same amount instead each time, instead of by doubling, then your insertion time becomes quadratic, which is bad!