Tower Defence - Path Finding
Learning about A* search algorithm.
Written the by Thomas Cairns.
Introduction
My tower defence implementation doesn't need path finding, since the map will be static. However there are two reasons I have spent the past few days learning about the topic:
- I have hardly any knowledge about the subject, specially not implementation details.
- It's a very common mechanic in games, knowing the basics feels important.
A*
When reading about path finding and 2D games, the A* (pronounced A star) algorithm was by far the most mentioned approach. The more I read the clearer it became that there are an infinite amount of specific implementation off A*. I think that the flexibility of the core concept is what makes it so popular, but to me it also became difficult to grasp what actually is the core. Based upon that I decided studied a few beginner tutorials, and implement them to learn through reverse engineering. The approach help quite a bit since I now feel that I understand the basics and can see multiple ways of doing modifications and/or expansions.
Understanding and Implementation
A summary of how I see that the A* algorithm works and it also describes how my current implementation works. Before searching begins there are three parameters that have to be defined.
- A grid map, where you know if a position can be traversed or not.
- A start node (position) within the grid.
- An end node (position) within the grid.
Then you have a recursive search that uses the start node as an entry point. Make this node as “closed”, meaning that this node will not be looked at again. Look at all adjacent nodes and select the node:
- That has the lowest estimated distance to the end. Usually referred to as “weight”.
- That can be walked upon.
- The state of the node isn't “closed”.
- Repeat until the end node or a dead end has been reached
- If dead end then go back and select the next node that fulfils the requirements
Flaws and Improvements
My implementation isn't very elegant and could be worked on a lot more. The biggest flaw is that there is no system to handle scenarios where two or more nodes have the exact same weight, this means that the path sometimes walks in a zigzag-pattern. There are a few solutions I've seen while looking around at other approaches to the algorithm. The solution that seemed the most promising to me, is that when you hit the scenario of equally weighted nodes you keep looking down those nodes until one path becomes lighter.
Separated Code
At first I started implementing path finding directly into my game project, however I decided to split it into a separate project, called pather. The reason being that I needed an easy method of testing different scenarios and visually see the results to verify that the algorithm was working as expected.
Screenshot from the path finding project.
- Green coloured square is the start node. Placed with mouse button right-click.
- Red coloured square is the end node. Placed with mouse button left-click.
- Blue squares are the path between start and end.
- Light-grey tiles are traversable.
- Grey tiles are not traversable.
Download
If you want to try the project out, you can download it, pather.zip. The map can be changed through the map.txt file, where 0 means that the node is not traversable and 1 means it is. However when playing with the application note that it isn't built to be robust. An example would be to have any other value then specified above. Another example would be to placing both the start and end node on none traversable nodes, will make the application crash.
The Actual Code
Note that I'm trying to test a naming convention that is similar to that used in the std-library. As well as two spaces are used for indentation to keep the code compact.
Header
#pragma once
#include <vector>
namespace pf {
enum class state {
Unknown, Open, Closed
};
struct point {
int x = 0;
int y = 0;
pf::point(int x, int y) {
this->x = x;
this->y = y;
};
bool pf::point::operator ==(const pf::point & rhs) const {
return (this->x == rhs.x && this->y == rhs.y);
};
};
struct node : public pf::point {
double distance_start = 0;
double distance_end = 0.0f;
bool walkable = false;
pf::state state = pf::state::Unknown;
pf::node * parent = nullptr;
pf::node(int x, int y, bool walkable) :
point(x, y),
walkable(walkable) {
};
pf::node(pf::point * point, bool walkable) :
pf::point(point->x, point->y),
walkable(walkable) {
};
double get_weight() const {
return distance_start + distance_end;
};
static double estimate(const pf::point * lhs, const pf::point * rhs) {
return std::sqrt(std::pow(rhs->x - lhs->x, 2) + std::pow(rhs->y - lhs->y, 2));
};
static bool compare_weight(pf::node * lhs, pf::node * rhs) {
return (lhs->get_weight() < rhs->get_weight());
};
};
std::vector<pf::point *> find_path(std::vector<std::vector<bool>> map, const pf::point & start, const pf::point & end);
bool search(std::vector<std::vector<pf::node *>> nodes, pf::node * node, pf::node * end_node);
std::vector<pf::node *> get_adjacent(std::vector<std::vector<pf::node *>> nodes, pf::node * fromNode);
};
Source
#include "stdafx.h"
#include "PathFinder.h"
#include <algorithm>
#include <array>
#include <cmath>
std::vector<pf::point *> pf::find_path(std::vector<std::vector<bool>> map, const pf::point & start, const pf::point & end) {
std::vector<std::vector<pf::node *>> nodes;
pf::node * start_node;
pf::node * end_node;
for (int y = 0; y < map.size(); y++) {
nodes.push_back(std::vector<pf::node *>(0));
for (int x = 0; x < map[y].size(); x++) {
pf::node * node = new pf::node(x, y, map[y][x]);
node->state = pf::state::Unknown;
node->distance_end = pf::node::estimate(node, &end);
nodes[y].push_back(node);
if (*node == start) {
start_node = node;
} else if (*node == end) {
end_node = node;
}
}
}
std::vector<pf::point *> path;
bool success = pf::search(nodes, start_node, end_node);
if (success) {
pf::node * node = end_node;
while (node != nullptr) {
pf::point * p = new pf::point(node->x, node->y);
path.push_back(p);
node = node->parent;
}
std::reverse(path.begin(), path.end());
}
for (auto row : nodes) {
for (auto node : row) {
delete node;
}
}
nodes.clear();
start_node = nullptr;
end_node = nullptr;
return path;
};
bool pf::search(std::vector<std::vector<pf::node *>> nodes, pf::node * node, pf::node * end_node) {
node->state = pf::state::Closed;
auto next_nodes = pf::get_adjacent(nodes, node);
std::sort(next_nodes.begin(), next_nodes.end(), pf::node::compare_weight);
for (auto next_node : next_nodes) {
if (next_node->x == end_node->x && next_node->y == end_node->y) {
return true;
} else if (search(nodes, next_node, end_node)) {
return true;
}
}
return false;
};
std::vector<pf::node*> pf::get_adjacent(std::vector<std::vector<pf::node *>> nodes, pf::node * node) {
std::vector<pf::node *> adjacent;
std::array<pf::point, 4> offsets{ {
{ node->x - 1, node->y },
{ node->x + 1, node->y },
{ node->x, node->y - 1 },
{ node->x, node->y + 1 }
} };
for (auto offset : offsets) {
if ((offset.y < 0 || offset.y >= nodes.size()) ||
(offset.x < 0 || offset.x >= nodes[offset.y].size())) {
continue;
}
pf::node * offset_node = nodes[offset.y][offset.x];
if (!offset_node->walkable) {
continue;
}
switch (offset_node->state) {
case pf::state::Closed: {
continue;
break;
}
case pf::state::Open: {
double distance_parent = pf::node::estimate(offset_node, offset_node->parent);
double new_estimate = node->distance_start + distance_parent;
if (new_estimate < offset_node->distance_start) {
offset_node->parent = node;
offset_node->distance_start = offset_node->parent->distance_start + pf::node::estimate(offset_node, offset_node->parent);
adjacent.push_back(offset_node);
}
break;
}
case pf::state::Unknown: {
offset_node->state = pf::state::Open;
offset_node->parent = node;
offset_node->distance_start = offset_node->parent->distance_start + pf::node::estimate(offset_node, offset_node->parent);
adjacent.push_back(offset_node);
break;
}
default:
break;
}
}
return adjacent;
};