Make tile-based A* (pathfind) node-based?

Started by
3 comments, last by wodinoneeye 9 years, 8 months ago

Hi

I have a a* that is tilebased. I now have a game with nodes that i place myself on a map (each with x/y pos and up to 8 neighboring/reachable nodes). I want to change the algoritm so it works with these arbitrary nodes instead.

Any tips or examples how to achieve this?

Thanks
Erik

Advertisement
A* works on arbitrary graphs, not just tiles. So you shouldn't encounter any problems when transitioning to your hand-placed nodes. If you do encounter some difficulties, tell us specifically what part you are having trouble with.

each with x/y pos and up to 8 neighboring/reachable nodes

OK but isnt your map more irregular than that with varying edges and chokepoints (portals) to be using that more generic 'network' of nodes ??

Anyway, if as implied in the highlight above you will still have a regular grid pattern overlaid over your tile type terrain so the same algorythm can be used (the distances/costs might be now derived/calculated preprocesed from the tiles).

Wont you still need a 'fine detail' pathfinding/navigation on the tiles themselves for object movement OR you are now navigating/moving only off lines of the course network --and are you sure that wont run into conflicts with some tiles (assume the edge lines are clear)?

A hierarchical pathfinding system can make longer path processing more efficient as long as you map is large enough to make the added complexity worth the trouble.

--------------------------------------------[size="1"]Ratings are Opinion, not Fact

hmm

nodes form a network, no need for portals. Ill have to try some more when i have time to see whats working and not. Thanks for the input.

hmm

nodes form a network, no need for portals. Ill have to try some more when i have time to see whats working and not. Thanks for the input.

Yes the nodes form a network except it might not be a regular 2D grid of times (being the nodes usually in a tile pathfinder).

Portals are the chokepoints (like in doorways or between other significant path blocking features).

The hierarchy is YOU seting these high level nodes avoiding the major blocking features and having much shorter patgh calculations (since the open list for A* can grow upto Distance^2 in mazelike terrain) So you have much more spread out (fewer) high level nodes to create a general path, and then actual movement using those high level node centers as destinations for much shorter fine (tile) grained A* your pathfinding processing would be significant (again if the distances and usage on you map system and game mechanics warrant using the more complicated 2 tier pathfinding.)

--------------------------------------------[size="1"]Ratings are Opinion, not Fact

This topic is closed to new replies.

Advertisement