Haunted Light – Pathfinding!
|
This was a hard nut to crack. And I’m not going to lie, our lead programmer, http://codergimmic.wordpress.com/, was extremely helpful with this, since he supplied me with A* pathfinding code from one of his projects. And so I analyzed that code and figured out the logic behind it. I also used this website to try and figure it out: http://www.policyalmanac.org/games/aStarTutorial.htm. I also read about A* at other sites, but those two sources were my main help in making this. For A* to work, your game have to use some kind of tile system for your map. A* uses a sort of economics to figure out where to go next. The system uses the objects current position on the tile system to find the CHEAPEST path from where it is to where it’s going. What I mean by cheapest is that A* doesn’t necessarily calculate the fastest path, purely on how many tiles the object have to move over to get to its goal, but takes into account the different types of tiles, ones that slows the object down “costs” more to walk over.
Now, about the cost. It works in a way that the 4 squares that are on your sides(up, down, left and right) costs 1 to go to. And from there the next step also costs 1 to another tile, making the total cost 2 to walk to one tile to another one 2 tiles away. And if you’re enabling the object to walk diagonally, the cost of one of those steps is roughly 1.41, it’s the square root of 2 since you technically take 1 step up and one sideways, but not really, it’s just 1 step that’s a bit longer that the others. So the cost is basically how many tiles away from the one you’re standing on the one you’re walking to is. But to some code goodies now, more specifically, how the pathfinding work from a code perspective. First and foremost, a set of nodes are created, each and every one represent a tile of your level. So there are as many nodes as there are tiles. The pathfinding works in a way that it looks through all the nodes around it and sets the one that is the closest to its target as its next one. If that node is a “blocked” node, a wall for example, then the object looks at the node that is the second closest to its target to see if that node is “open”, a walk-able tile. And A* does that the whole way to the target node, to form a path for the object to go. There nodes that it’s going to go through gets inserted into a list, or a vector to be precise, that tells the object to what node it’s going to next. I’m going to end this post the way I started it, it was a really hard nut to crack and if I could go back a week to when I planned that I was going to do this, I would tell myself to read up on it twice as much as I did. And that is my tip for you as well, read up on A* before even starting coding it, and when you think you know enough to start coding it, read as much about it as you just did. Regards |
