Sorry your browser is not supported!

Hi guys!
Doy you have a simple alternative to A* aglorithm?
It is only a 10x10 grid and I need to save time

EDIT: The grid consists of cells only with "EMPTY" or "NON EMPTY" states (TIER 1 implementation)

You could use a flood fill. Like, using a 2D array 10x10, set all the values to 100, then the destination to 0. Then, scan through the array and when it's EMPTY, set the value to the lowest neighboring value +1, so the grid location next to the destination would be 1. Repeat that, top left to bottom right, bottom right to top left will speed things up.

Do that until the array location at the enemy position contains a value <100... then check the surrounding values for the lowest one that is less than the current location value. Basically, the array will contain the number of positions to the destination, head towards the lowest value position and the enemies will know the shortest 8 direction route to the destination.

Maybe just do 1 pathfinding check per loop, let the enemies have an idle state, or just go to a random location until they find the path. With just 1 check per loop, it'll probably be solved in well under a second, and won't cost a great deal performance wise.

I would suggest making the array 12x12 though, leave a 1 unit gap around the edges, then you can avoid doing range checks, like make the border solid, then only scan the array from 1 to 10 - then doing x-1,y+1 etc style array checks don't need to make sure they're within the array range. This might save a little performance as well.

Thanks, I'll try and if I have a nice working code I will share it with the community

Breadth-first search is something you might want to consider.

what about if enemy is moving? Is the flood fill algorithm still valid?

Yes, what you'd end up with is an array map that leads to the player from any location, the enemy just has to check the array values at their location and head towards the lowest value to find the player.

All the cells or only the EMPTY cells?


What value should I set in the starting location?


In which location I will start the scanning?


You mean a clockwise rotation?

I don't think it matters too much if you just set everything to 100, just depends on how you check the walls when calculating the path. Like, it might be safer to just check a separate map array for collision, rather than relying on a set value for a wall. Once the path calculation is complete, the walls should all be still set to 100.

There is no starting location - because it's such a small map, you might as well solve the path for every location, the flood fill system will do that - basically the path array will be filled completely, so you could start at any location and find the destination. I would just keep setting the array for the player position to 0, run through the routine once or twice, and do that each loop - and there would be a constant pathway to the player that updates automatically. If you set a map location to have no wall, like opening a door, then it would even allow for that.

When scanning the array, I'd do something like this:

For x=1 to 10
For z=1 to 10
If map[x,z]<>wall
near=100
If path[x-1,z] < near then near=path[x-1,z]
If path[x+1,z] < near then near=path[x+1,z]
If path[x,z-1] < near then near=path[x,z-1]
If path[x,z+1] < near then near=path[x,z+1]
path[x,z]=near+1
Endif
Next z
Next x

But then change up the order that the array is scanned, like...

For x=1 to 10
For z=1 to 10
...
Next z
Next x

For z=1 to 10
For x=1 to 10
...
Next x
Next z

For x=10 to 1
For z=10 to 1
...
Next z
Next x

For z=10 to 1
For x=10 to 1
...
Next x
Next z

So it goes vertical stripes, horizontal stripes, reverse vertical, reverse horizontal. This is not 100% vital, what it actually does is improves the functions ability to calculate corridors quickly, like a long line of blank map, no matter how long, would be filled with the path data within 1 set of passes. If you use another variable to step through, then you could use a counter to decide which direction, and just set X and Z depending on that, that's one way to avoid repeating the same path code 4 times.


I have done this with a dungeon game project, it turned out to be too basic for a 3D dungeon crawler - but for a top down maze it should be ideal. I'll see if I can knock up a little example of this for you.

Thank you very much Van B. You've already help alot!