   Range Sight Algorithm - Is There A Faster One?
  Hi,I used the following algorithm in my flash game:http://www.gamedev.net/reference/articles/article724.aspIt took almost no time when I set the Movement Limit to 4 or less. Then it got about 5 times slower everytime I increase the Movement Limit by 1:Movement Limit: 5Time Taken: 1 secondMovement Limit: 6Time Taken: 5 secondsMovement Limit: 7Time Taken: 25 secondsIs there a faster algorithm available? Any suggestion appreciated.Thanks[Edited by - Nick123 on January 21, 2008 7:47:27 AM]
  I'd guess that your algorithm is checking every move more than once.  Adding 1 more movement shouldn't cause the execution time to go up exponentially.  If you post some code, someone can probably help.   ;  I just tested this sample with a bigger map:http://www.tonypa.pri.ee/tbw/tut22.htmlIt use almost the same algorithm and the results are similar:Movement: 13Time: 7 secMovement: 14Time: 28 secI think 4 times will be more exact.   ;  There was a thread where there was a visibility algorithm that traversed all the hexes at once, so to speak.  I'll see if I can find it...Here it is in the AI forum.   ;Quote:Original post by ID MerlinThere was a thread where there was a visibility algorithm that traversed all the hexes at once, so to speak.  I'll see if I can find it...Here it is in the AI forum.It's a visibility algorithm, but I was looking for an algorithm that, given a location of a unit, would tell you what locations can be reached in the next turn.Thanks   ;  What's your current algorithm? Maybe it'll be something we can point out, or a logical error you hadn't noticed.A* will work just fine; it's the general-form algorithm for problems like these. You can also brew up a more specific algorithm using the A* implementation as a reference if you want.   ;  Sounds like you could do it with a Breadth first search.   ;  if intelligence==any{use_gm(1)}