Jump to content
  • Advertisement
Sign in to follow this  

A* Pathfinding, or alternative?

This topic is 3715 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello! I'm kind of stuck on my battle-scenes which use tile by tile movement, kinda like a Tactical RPG, for example the game; Fire Emblem (GBA series) (Little youtube movie about the gameplay, note the movement on the map)
Now, I've read about A* Pathfinding, but I've been looking into and have barely been able to find understandable code-examples from, and only explaining in words how to implement it doesn't really do me good right now, so I was wondering if anyone had any information, understandable code example(s) or an alternative to this? Thanks in advance! :]

Share this post


Link to post
Share on other sites
Advertisement
What is it exactly that you find difficult to understand about A*?

If everything you have read until now did not help you, I doubt that pointing you to anything will make it better, so by addressing your confusion directly, it maybe works better ...

Share this post


Link to post
Share on other sites
For grid-based movement A* should work very well, and is pretty trivial. I've seen it implmented with lists, 2D arrays, and trees. All you need to do is keep trace of which tiles are on the open list and which are on the closed list, then loop through them, along with the scores for each tile.

Which language are you trying to do this in, anyway?

Share this post


Link to post
Share on other sites
Quote:
Original post by Auriya
Now, I've read about A* Pathfinding, but I've been looking into and have barely been able to find understandable code-examples from, and only explaining in words how to implement it doesn't really do me good right now, so I was wondering if anyone had any information, understandable code example(s) or an alternative to this?


It's a progressive heuristic.

Write your own pathfinding code, and you would either have something better, or reinvent it anyway.

With FEIV like games the problem is more in clogging choke points than pathfinding.

Share this post


Link to post
Share on other sites
Hi!

This guide is really well explained and should get you up and running!

http://www.gamedev.net/reference/articles/article2003.asp

Note that there's no code in the tutorial, but each step of the pathfinding is thoroughly explained.

/Robert

Share this post


Link to post
Share on other sites
Another site with LOTS of info, although a bit messy to look at!

http://www.gameai.com/ai.html

Check Software Solutions for code, but this unfortunaly won't get you far without knowing the algorithm properly...

Share this post


Link to post
Share on other sites
A* is a pretty straightforward algorithm, but it took me two or three readings before it 'clicked' and I went 'duh!' and wrote some code.

Basically all it is is that each step you find the most promising tile you've already determined is reachable, and then add all the possible places you could move in one step from that tile to the list of reachable tiles. 'Most promising' usually means 'distance travelled to get there + estimated distance to finish'.

I have some c# code but to be honest, it's probably not helpful to give code. Once you 'get' it, writing code will be trivial.

Share this post


Link to post
Share on other sites
If you're still interested in alternatives, think about IDA* and Fringe search. There are more details within this thread:

http://www.gamedev.net/community/forums/topic.asp?topic_id=471712&PageSize=25&WhichPage=1


I won't rehash all the details that are already in that thread, but let me know if you have questions. Also, I have an article in the most recent Game Programming Gems 7 that discusses A*, IDA* and Fringe search.

-Kirk

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!