Jump to content

  • Log In with Google      Sign In   
  • Create Account


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

  • You cannot reply to this topic
4 replies to this topic

#1 suliman   Members   -  Reputation: 551

Like
0Likes
Like

Posted 22 August 2014 - 11:51 PM

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



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12844

Like
1Likes
Like

Posted 23 August 2014 - 06:40 AM

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.

#3 wodinoneeye   Members   -  Reputation: 742

Like
0Likes
Like

Posted 23 August 2014 - 07:38 PM

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.


--------------------------------------------Ratings are Opinion, not Fact

#4 suliman   Members   -  Reputation: 551

Like
0Likes
Like

Posted 24 August 2014 - 10:36 AM

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.



#5 wodinoneeye   Members   -  Reputation: 742

Like
0Likes
Like

Posted 25 August 2014 - 09:04 AM

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.)


--------------------------------------------Ratings are Opinion, not Fact





PARTNERS