Tower Defence – Path Finding
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 start) 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.
A summary of how I see that the A* algorithm works:
is that you have three basic parameters:
- A grid map, where you know if a position can be traversed or not
- A start node (position) within the grid
- A end node (position) within the grid
Then you have a recursive search that uses the start node as an entry point:
- Look at all adjacent nodes and select the nodes that can be traversed
- Sort the nodes based on estimate the distance to the end node
- Repeat the process but use the node with the lowest estimate as a the base
- Either the end will be reached or the path discarded because it was a dead end
The above description is of course a simplification.
The description doesn’t contain information about state tracking, which makes it possible to discard and try different branches, and it doesn’t explain how the actual path is stored either.
It’s also possible to make the search more interesting by introducing an additional “weight” to each node that makes the search prefer a node over another even though the distance to the end is estimated to be equal.
My understanding
Setup:
- Define a grid map
- Specify a start position within the grid
- Specify an end position within the grid
Search:
- Make this node as “closed”, meaning that this node will not be looked at again
- Look at all adjacent nodes
- Select the node:
- That can be walked upon
- The state of the node isn’t “closed”
- With the lowest estimated distance to the end
- Repeat until the end node or a dead end has been reached
- If dead end then go back and select the next node that fulfills the requirements
Implementation
My current implementation isn’t very elegant and could be worked on a lot more.
The biggest flaw right now is that there is no system to handle scenarios where two or more nodes have the same weight.
I will definitely come back to the code and work on it in the future, but as I said earlier I don’t really need a path finder and if I use one it can be very crude since the path will not be very complex.
Also note that the search only links to nodes that are in direct horizontal or vertical positions and not diagonally, I don’t want my units to walk across a corner in the map.
At first I started implementing the path finding directly into the game project, however I decided to split it into a separate project.
The reason being that I needed an easy method of testing different scenarios and visually see the results to verify that the algorithm works 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
#pragma once
#include
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);
};
Cpp-file
#include "stdafx.h"
#include "PathFinder.h"
#include
#include
#include
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;
};
About Thomas Cairns
2016 Programming
|
