HOME | DD

Description
So I've come to the point in my development where the basics of the battle system are complete and the inventory systems are basically complete - few things missing here and there.

Then I was debating with myself how to make the overworld in my game, and I settled with a click based movement system - since it's not a real-time swordplay game like Zelda, but a turn-based RPG like Final Fantasy, I thought I might aswell make the overworld clickable. I started reading about graph search algorithms and pathfinding in my book "Algorithms In A Nutshell", and I settled with using A* pathfinding, which is a great algorithm that finds a path based on a heuristic. What in the world is a heuristic, you may ask, and I didn't know either at first, but I found out it's a method in which the search algorithm (we're performing a search of the destination tile from the source tile) in which we calculate the direction of the destination compared to the current position and compared to the source tile, and settle with the direction with the least cost. The great thing about A* search is that it only searches in areas of the map the algorithm finds wise to look in, for example the Dijkstra's algorithm searches the whole map and finds a path, which will result in worse performance since we want a game to run fast, so A* is a better solution in this case.

Wikipedia has a great visualization of both A* and Dijkstra:
Dijkstra: [link]
A*: [link]

As you can see in the two examples above, A* looks through a lot less nodes (tiles) than Dijkstra, so it is more efficient, as I just want to find a good path, fast.

I'm considering precalculating paths for the final game when the final maps are made, which means all possible paths will be precalculated by me outside the game, and path lookup will be blitzingly fast.

I must warn you, you may click on a tile that's so far away it might take a few seconds to compute the path, but I'm not sure, when I've been testing this in a browser it's been running faster than in Flash, so I'm not entirely sure.

I hope you enjoy this example of A* pathfinding.

Description
So I've come to the point in my development where the basics of the battle system are complete and the inventory systems are basically complete - few things missing here and there.

Then I was debating with myself how to make the overworld in my game, and I settled with a click based movement system - since it's not a real-time swordplay game like Zelda, but a turn-based RPG like Final Fantasy, I thought I might aswell make the overworld clickable. I started reading about graph search algorithms and pathfinding in my book "Algorithms In A Nutshell", and I settled with using A* pathfinding, which is a great algorithm that finds a path based on a heuristic. What in the world is a heuristic, you may ask, and I didn't know either at first, but I found out it's a method in which the search algorithm (we're performing a search of the destination tile from the source tile) in which we calculate the direction of the destination compared to the current position and compared to the source tile, and settle with the direction with the least cost. The great thing about A* search is that it only searches in areas of the map the algorithm finds wise to look in, for example the Dijkstra's algorithm searches the whole map and finds a path, which will result in worse performance since we want a game to run fast, so A* is a better solution in this case.

Wikipedia has a great visualization of both A* and Dijkstra:
Dijkstra: [link]
A*: [link]

As you can see in the two examples above, A* looks through a lot less nodes (tiles) than Dijkstra, so it is more efficient, as I just want to find a good path, fast.

I'm considering precalculating paths for the final game when the final maps are made, which means all possible paths will be precalculated by me outside the game, and path lookup will be blitzingly fast.

I must warn you, you may click on a tile that's so far away it might take a few seconds to compute the path, but I'm not sure, when I've been testing this in a browser it's been running faster than in Flash, so I'm not entirely sure.

I hope you enjoy this example of A* pathfinding.