Itutorial
Legendary OT User
- Joined
- Dec 23, 2014
- Messages
- 2,336
- Solutions
- 68
- Reaction score
- 1,018
Alright guys. As you know i've been working on the A* algorithm for TFS.
I have most of the code ready. I am just having some trouble with the logic and algorithm. Hopefully, someone will be able to see something I cant.
Right now the code works left/down. It doesn't work up/right. When the targetPos is up/right (north/east) the code doesn't work.
It is also favoring diagonal movements for some reason but does work properly when its a straight line to the target.
Here it is...
map.h
map.cpp
I have most of the code ready. I am just having some trouble with the logic and algorithm. Hopefully, someone will be able to see something I cant.
Right now the code works left/down. It doesn't work up/right. When the targetPos is up/right (north/east) the code doesn't work.
It is also favoring diagonal movements for some reason but does work properly when its a straight line to the target.
Here it is...
map.h
C++:
static constexpr int_fast32_t MAP_NORMALWALKCOST = 10;
static constexpr int_fast32_t MAP_DIAGONALWALKCOST = 25;
static int_fast32_t allNeighbors[8][2] = {
{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}
};
struct AStarNode
{
AStarNode* parent = nullptr;
int_fast32_t f;
int_fast32_t fGlobal;
uint16_t x, y;
bool visited = false;
};
class AStarMap
{
public:
AStarMap(uint16_t x, uint16_t y, uint8_t z);
AStarNode* getNodeByPosition(uint16_t x, uint16_t y);
AStarNode* addNode(uint16_t x, uint16_t y);
void addOldNode(AStarNode* node) {
nodes.push_front(node);
}
static int_fast32_t getMapWalkCost(AStarNode* node, const Position& neighborPos);
static int_fast32_t getTileWalkCost(const Creature& creature, const Tile* tile);
std::forward_list<AStarNode*> getNodes() {
return nodes;
}
private:
std::forward_list<AStarNode*> nodes;
uint16_t x, y;
uint8_t z;
};
map.cpp
C++:
bool Map::getPathMatching(const Creature& creature, const Position& targetPos, std::vector<Direction>& dirList,
const FrozenPathingConditionCall& pathCondition, const FindPathParams& fpp) const
{
Position pos = creature.getPosition();
Position endPos = targetPos;
const Position& startPos = pos;
// Don't update path if the target is too far away
if (Position::getDistanceX(startPos, endPos) > fpp.maxSearchDist || Position::getDistanceY(startPos, endPos) > fpp.maxSearchDist) {
return false;
}
// Create an AStarMap class to store our nodes.
AStarMap map(startPos.x, startPos.y, startPos.z);
int32_t bestMatch = 0;
AStarNode* found = nullptr;
// Create our start node
AStarNode* startNode = new AStarNode();
startNode->parent = nullptr;
startNode->f = 0;
startNode->fGlobal = std::numeric_limits<int32_t>::max();
startNode->x = pos.x;
startNode->y = pos.y;
// List to hold open nodes that need to be checked for a path
std::list<AStarNode*> openNodes;
// Add start node to nodes list
map.addOldNode(startNode);
// Add start node pointer to openNodes
startNode = map.getNodeByPosition(pos.x, pos.y);
openNodes.push_back(startNode);
// While we have nodes to check or we haven't found the end.
while (!openNodes.empty() || !found) {
// Sorted Open list. Lowest fGlobal cost is at top.
openNodes.sort([](const AStarNode* lhs, const AStarNode* rhs) { return lhs->fGlobal < rhs->fGlobal; });
// Set the parent node to the first openNode : openNodes[0]
AStarNode* parentNode = openNodes.front();
// Remove nodes we already checked
while (parentNode->visited) {
openNodes.pop_front();
parentNode = openNodes.front();
}
// Set the parent as visted and set its x/y to check neighbours
parentNode->visited = true;
pos.x = parentNode->x;
pos.y = parentNode->y;
// Path call to see if we are within the range of where we should be.
if (pathCondition(startPos, pos, fpp, bestMatch)) {
found = parentNode;
endPos = pos;
if (bestMatch == 0) {
break;
}
}
// Start checking parent nodes neighbours
for (uint32_t i = 0; i < 8; ++i) {
pos.x = pos.x + allNeighbors[i][0];
pos.y = pos.y + allNeighbors[i][1];
// We can't walk on this tile so lets ignore it
const Tile* tile = getTile(pos.x, pos.y, pos.z);
if (tile->hasFlag(CONST_PROP_BLOCKPATH) || tile->hasFlag(CONST_PROP_BLOCKSOLID)) {
continue;
}
// Get this neighbour if it exists in map->nodes list.
AStarNode* neighbour = map.getNodeByPosition(pos.x, pos.y);
// All different types of variables to determine the alogirthm.
const int_fast32_t walkCost = AStarMap::getMapWalkCost(parentNode, pos);
const int_fast32_t tileCost = AStarMap::getTileWalkCost(creature, tile);
// New nodes distance to x
const int_fast32_t nodeDistTarget = Position::getDistanceX(pos, targetPos) + Position::getDistanceY(pos, targetPos);
const int_fast32_t nodeDistStart = Position::getDistanceX(pos, startPos) + Position::getDistanceY(pos, startPos);
// Parents node distance to x
const Position cNodePos(parentNode->x, parentNode->y, pos.z);
const int_fast32_t parentDistTarget = Position::getDistanceX(cNodePos, targetPos) + Position::getDistanceY(cNodePos, targetPos);
const int_fast32_t parentDistStart = Position::getDistanceX(cNodePos, startPos) + Position::getDistanceY(cNodePos, startPos);
const int_fast32_t parentDistNode = Position::getDistanceX(cNodePos, pos) + Position::getDistanceY(cNodePos, pos);
// Create F cost
const int_fast32_t f = nodeDistStart + nodeDistTarget + (walkCost + tileCost);
g_game.addMagicEffect(pos, CONST_ME_POFF);
if (!neighbour) { // This is a new node.
AStarNode* neighbour = new AStarNode();
neighbour->parent = parentNode;
neighbour->x = pos.x;
neighbour->y = pos.y;
neighbour->f = f;
neighbour->fGlobal = nodeDistTarget;
map.addNode(pos.x, pos.y);
openNodes.push_back(neighbour);
} else { // This is a previous neighbour node
if (f < neighbour->f) {
AStarNode* lastParent = neighbour->parent;
if (lastParent && parentNode->fGlobal < lastParent->fGlobal) {
neighbour->parent = parentNode;
neighbour->f = f;
neighbour->fGlobal = parentNode->fGlobal;
openNodes.push_back(neighbour);
}
}
}
}
}
// !! THIS AND BELOW WORKS FINE !! //
if (!found) {
std::cout << "COULD NOT FIND PATH" << std::endl;
return false;
}
uint_fast32_t prevx = endPos.x;
uint_fast32_t prevy = endPos.y;
found = found->parent;
while (found) {
g_game.addMagicEffect(pos, CONST_ME_TELEPORT);
pos.x = found->x;
pos.y = found->y;
uint_fast32_t dx = pos.getX() - prevx;
uint_fast32_t dy = pos.getY() - prevy;
prevx = pos.x;
prevy = pos.y;
if (dx == 1 && dy == 1) {
dirList.push_back(DIRECTION_NORTHWEST);
}
else if (dx == -1 && dy == 1) {
dirList.push_back(DIRECTION_NORTHEAST);
}
else if (dx == 1 && dy == -1) {
dirList.push_back(DIRECTION_SOUTHWEST);
}
else if (dx == -1 && dy == -1) {
dirList.push_back(DIRECTION_SOUTHEAST);
}
else if (dx == 1) {
dirList.push_back(DIRECTION_WEST);
}
else if (dx == -1) {
dirList.push_back(DIRECTION_EAST);
}
else if (dy == 1) {
dirList.push_back(DIRECTION_NORTH);
}
else if (dy == -1) {
dirList.push_back(DIRECTION_SOUTH);
}
found = found->parent;
}
return true;
}
// AStarMap
AStarMap::AStarMap(uint16_t x, uint16_t y, uint8_t z)
{
x = x;
y = y;
z = z;
}
AStarNode* AStarMap::getNodeByPosition(uint16_t x, uint16_t y)
{
for (auto node : nodes) {
if (node->x == x && node->y == y) {
return node;
}
}
return nullptr;
}
AStarNode* AStarMap::addNode(uint16_t x, uint16_t y)
{
AStarNode* newNode = new AStarNode();
newNode->x = x;
newNode->y = y;
return newNode;
}
Last edited: