Solved - Need advice/guidance on path finding - A*

Newbie & Debugging Questions
#1

Hi guys,

So I have recently been looking into path finding as I would like to add it to my arsenal of game development skills. I’ve been looking into A* specifically but i’m getting confused and need some guidance or more resources to look through.

I’ve been reading about the different areas that allow A* to work the way it does, such as H, G and F values. I found some pretty good resources, but not many that I found seemed to cover everything from the complete beginner perspective and those that did seemed to be badly done. I found a few helpful videos on the subject as well, where the person went through how the path finding works and this has helped a lot. I’m struggling to find some code written in Java so I can read through it and get a better understanding before I attempt my own path finding solution.

If anyone knows of any resources/code snippets that could help me understand A* better I would really appreciate it :point:

#2

http://www.policyalmanac.org/games/aStarTutorial.htm

#3

i can recommend http://www.ai-junkie.com/

very clear and beginner friendly introduction into game-ai coding in general. grab the book (programming AI by example) if you can. he’s dedicating a chapter to pathfinding (chapter 5 : graph theory). all the stuff from basic graph-traversal to A*. (ja, cylab i still have it!)

start with something more easy and plain then A* tbh. even if it’s inefficient and brute force, you will get the basic better when you go through the matter step by step. it doesn’t take too long even :wink: in the end you will understand and know why A* is the best choice.

you can find a java port of the c++ sourcecode from this book here : http://www.sallyx.org/sally/en/game-ai/

#4

I can recommend “Programming Game AI by Example” too, although I’m only around 60 pages in or so, it seems really promising.
Although if you don’t need anything deeper than a simple A* than go with trollwarrior1’s link, that’s possibly the best explanation online.

#5

Thank you for the advice and links guys :slight_smile: I’ve read through what Warrior linked and I must say, it’s brilliant. I have one question that I couldn’t seem to find the answer to and then i’m going to attempt the coding.

I’m using a Tiled map and was wondering what the best way would be to use the map as nodes? I’m thinking something along the lines of grabbing the map width and height and then making each cell a node?

#6

The node value is basically the X and Y coordinate for a tiled grid.

Cas :slight_smile:

#7

yes, it’s the easiest approach. node = cell center, connecting surrounding cells with 4 (axis aligned) or 8 (if you want to go also diagonal) edges.

now make a screenshot :wink:

#8

Sadly I haven’t been able to implement the path finding yet. I understand the theory behind it and spent a lot of time yesterday on messing around with code to get a better understanding of how everything works.

I am still however am getting really confused about the node idea… I have no idea why this is confusing me but I can’t grasp the concept. At the moment I make my code get the map height and width and then make each cell on the map create a new Node that contains the position, width and height of each cell and add them all to a list. I grab the node I want to with start from the original list of available nodes and add it to the open list and set the target node equal to the node I want the finish at, this is also done using a node form the original list. I think the next thing to do it grab each nodes neighbours and then that is where I get the lowest f values, set the nodes parents, if the neighbour is on the list or if it isn’t on the list etc. Is this the correct way of doing things?

#9

Okay so the code is now working, allowing horizontal and vertical movement. I looked on Coke and Code as I feel I tried my best to fix the issue but sadly wasn’t able to fix it myself :frowning: but saying that, I learned about some of the following things:

  • I now know how to create the amount of available nodes for the map using my Tiled based map
  • I’m able to calculate the g, h and f costs and now know how to get each nodes neighbours
  • I have a better understanding of AI and can hopefully expand on this knowledge.

I’m planning on going over the code and making sure I understand what everything is doing and then will be deleting the code and starting from scratch, implementing some different features to make sure i’m not just coping from memory.

Thanks for everyone’s help :slight_smile:

#10

Which path does your code find for the following graph:


  B
 / \
A---D
 \ /
  C

Start: A, Destination: D

Weight for edge A→B: 1
Weight for edge A→C: 2
Weight for edge B→D: 3
Weight for edge C→D: 1
Weight for edge A→D: 6

Correct path is A→C→D

This test-case catches most common mistakes - both in searching and in backtracking.

#11

@Riven I’ll have to get back to you on this D: i’m currently adding in some code to stop an array out of bounds exception.

I do have a question about the speed of path finding. My current game is based on the game 'Super Smash TV (See link below)

ITwxViBUI0k

I’m planning on making each enemy find the player location and move to it but i’m worried about the effect it will have on performance due to the player moving around a lot and having a high number of enemies on the screen. Should I be recalculating a path each time the player moves or will this cause problems?

#12

If you haven’t already, you should check out this playlist. He explains graphs, Dijkstra’s, and A*.

#13

What helped understanding pathfinding was to do some simple examples using a pen and paper.

Draw a small network and then pick two nodes of the network and do the pathfinding by hand.

For example you could use following network:

Start with some simple cases (what is the nearest path from A -> D, I -> E) and when you get that right than try out a longer path (A -> H). For starting you might even chose a simpler network, like the one riven has posted. The algorithm stays the same, so if you get it right with a small example you should be able to do it with a bigger, more complex one.

The most important part from my perspective is that you understand what you are doing. By your profile your coding experience is not that long. I can imagine that you might be having issues with some language specific things that don’t have anything to do with the problem itself. I don’t see much sense in starting to code when you don’t get the theory/idea behind an algorithm. Understand the theory behind it first. If you know exactly what you want to implement you can work out the other problems more easily. (btw, this is also how we learned this in school. understanding the theory by solving some examples by hand, then getting the code up and running :wink: ).

Hmm, interesting. Need to have a look at this.

#14

Thank you for the extra advice and links guys, I really appreciate all the help you give :slight_smile:

The only issue I have now is making my enemy move along the path to the player, which is now updating depending on the player location :)! After this I should be done! Just need to tidy up and optimize the code

#15

Update: I’ve started work on making the enemies move to the player location and the video below shows it in action. The red bars on screen show the path and the enemy will follow it. They roll off the screen when the path is completed, this is for debugging, of course. The code needs some tweaking as I’ve noticed some errors when testing such as taking a slightly longer path and I also need to change the way it moves to each step of the path, as well as slowing the movement down.

JkgSXs6Lgfs

#16

What you have done is cool , the movement is accurate , one thing though is that when the play seems to make a sudden move change close to the ai the ai gets confused moves away then comes back . Maybe instead of continually updating the position maybe update it 1 every n ticks so that its not constantly adjusting and that it can get closer to the path the player is following.

#17

Thanks :slight_smile: I’ve noticed the change myself actually and i’m working on a fix. Below I’ve attached a video of the new path finding which is much smoother and slower.

I’m really not happy about the way in which the enemies move to the player location at the moment so if anyone has any suggestions, I’d love to hear them (I’m currently storing the steps in an arraylist and creating a vector that points to the next step the enemy needs to take).

H4MMADZi4JI

#18

I’m having some issues with tracking the path that I can’t seem to fix.

In my last post I had my path finding almost completed but I’ve come across a few issues. The first was the movement was sometimes diagonal, even though I didn’t want that. I also had an issue with the path being made slightly longer than it should have on certain occasions.

If someone could link me some code of retracing the path and moving an entity, I would be really grateful :)! I’ve tried a lot of different things D: