A* alternatives?
BlitzMax Forums/BlitzMax Programming/A* alternatives?
| ||
| does anyone know of other pathfinding routines and their disadvantages/advantages? Tbe only problem I have with A* is that it has to look at every square on the map to detect a fail and it can slow things down a little bit. |
| ||
| You can combine a* with other things, like using quadrants. |
| ||
| And if the route doesn't change, then can't you simply cache it and recalculate it only when you need to? I've also implemented a method of spreading out recalculations over time, where things further away would update later than things closer to the point of change, which helped to keep the framerate max'd out. |
| ||
| As long as you need to always find the path when there is one, A* will look at every square before failing. However, if you can accept it failing to find some paths, you can put limits to path length, eg. based on the direct distance between two squares. |
| ||
| Also, it is a really good idea to split up the search. You should create a path planner and everything that needs to find a path sends the information to it. The path planner will search only X tiles every frame, for every path needed. When a solution is found, or none, it will send a message to the entity requesting the path. |
| ||
| Tbe only problem I have with A* is that it has to look at every square on the map to detect a fail and it can slow things down a little bit. The something is wrong and suggest your heuristic is not set correctly. What you describe is Dijkstra's Algo. this is very good at describing the different methods. p.s. Depending on the type of map you can also use Steering Behaviours to do pathfinding. |
| ||
| Other well-known path finding algorythms are Hill Climbing and Best First (a Google search should give you more info about them). The thing about A* is that it is guaranteed to give the shortest path in the most efficient way (as long as the heuristic value is computed correctly and you give reasonable values to node depths). If you don't care about getting the best path, another search method may do the work, if you want the best path, then A* is the way to go. |
| ||
| If you optimize your A* you should be able to process thousands of npcs no problem. I have run game servers that have done this without any issues on a fairly slow cpu. you can put limits to path length Extremely important. Also what brucey said about recalculations is a great idea, if necessary. If you don't have any dynamic tile entities (block tiles aren't moving) then this is highly suggested. The only thing you would need to calculate per move is whether a player/npc is in the next location, which can be detected using arrays containing the ID of the player/npc in the way. If array[map].spot[x,y] > 0 then {Must recalculate, or attack?}. If no players have been in a map or area for a long time, disable the npcs ai. |
| ||
| i have doors that can be locked, so i think pre-calculated routes will not work, ill have to check out hillclimbing and best first thanks |
| ||
| so i think pre-calculated routes will not work They are not required. I don't know how intsense your game is on pathfinding, but I doubt with optimization that you'll overpower a*, especially with path limitations (which is extremely easy to impliment). If your game is multiplayer, you'll probobly smack your bandwidth before a* movement processing. If you don't need 'good' pathfinding, then go ahead with checking out others, otherwise you have nothing to lose with a-star, just limit range and path calculation counts and you'll be more then fine. |
| ||
| I think here's where multi-threading would come in handy. If you had a thread running your algorithm, your program would be free perform other duties. Too bad BRL has ruled out multi-threading in BMax. |
| ||
| yup |
| ||
| Jeremy, If your map is made up of various rooms with doors (or just doorways) between them, then you can have a two-level pathfinding system. What I mean is, first find the shortest path between the rooms. To do this, each room is a node in the first level of pathfinding. If the character is in the same room as the destination location, then switch to level two pathfinding, which is more detailed with a grid on the floor. Most of the time, once the character is in the room, there will be a straight line to the destination unless your individual rooms are like mazes. Dividing your map up by rooms is basically the same idea as using quadrants like smilertoo said. |
   |