Skip to content

Instantly share code, notes, and snippets.

@zugdud zugdud/dijkstra.cpp
Created Oct 24, 2016

Embed
What would you like to do?
struct MatrixPosition
{
int y;
int x;
};
struct orderLeastWeight
{
inline bool operator()(const WeightedNode& weightedNode1, const WeightedNode& weightedNode2)
{
return (weightedNode1.weightValue < weightedNode2.weightValue);
}
};
struct WeightedNode
{
int nodeId;
int weightValue;
};
struct orderLeastWeight
{
inline bool operator()(const WeightedNode& weightedNode1, const WeightedNode& weightedNode2)
{
return (weightedNode1.weightValue < weightedNode2.weightValue);
}
};
// The Weighted queue always returns the lowest weight value node from get()
class WeightedQueue {
public:
WeightedQueue();
int get(); // return the item with the lowest weight value and remove it from the map
void push(int weight, int NodeId); // add item
bool empty(); // is it empty
private:
std::vector <WeightedNode> mNodeVec; // nodeId
};
WeightedQueue::WeightedQueue()
{
}
void WeightedQueue::push(int weightValue, int nodeId)
{
WeightedNode weightedNode;
weightedNode.weightValue = weightValue;
weightedNode.nodeId = nodeId;
mNodeVec.push_back(weightedNode);
std::sort(mNodeVec.begin(), mNodeVec.end(), orderLeastWeight());
}
bool WeightedQueue::empty()
{
return mNodeVec.empty();
}
int WeightedQueue::get()
{
int nodeId = mNodeVec.begin()->nodeId;
mNodeVec.erase(mNodeVec.begin());
return nodeId;
}
void Board::setMatrixPositions()
{
for (int i = 0; i < mTileCount; i++)
{
MatrixPosition matrixPosition = { i / mTileRows, i % mTileRows };
mMatrixPosition[i] = matrixPosition;
}
}
int Board::getTileId(MatrixPosition matrixPosition)
{
int tileId = mTileRows * matrixPosition.y + matrixPosition.x; // left to right
return tileId;
}
// reconstruct the path taken
void Board::setPath(int startTileId, int endTileId, AIStrategy aiStrategy, std::map<int, int> & cameFrom)
{
std::vector<int> path;
int currentTileId = endTileId;
path.push_back(currentTileId);
while (currentTileId != startTileId)
{
currentTileId = cameFrom[currentTileId];
path.push_back(currentTileId);
}
std::reverse(path.begin(), path.end()); // invert order to be start->end
if (path.size() >= 2)
{
mTileMap[startTileId]->setPath(aiStrategy, path[1]); // set path to the first move
}
}
// [ 0][ 1][ 2][ 3][ 4]
// [ 5][ 6][ 7][ 8][ 9]
// [10][11][12][13][14]
// [15][16][17][18][19]
// [20][21][22][23][24]
void Board::collectNeighbors(int tileId, std::vector<int> & neighbors)
{
MatrixPosition tile = getMatrixPosition(tileId);
const int x = tile.x;
const int y = tile.y;
// up
if (y > 0)
{
int up = y - 1;
int neighborTileId = getTileId(x, up);
neighbors.push_back(neighborTileId);
}
// down
if (y < mTileRows - 1)
{
int down = y + 1;
int neighborTileId = getTileId(x, down);
neighbors.push_back(neighborTileId);
}
// left
if (x > 0)
{
int left = x - 1;
int neighborTileId = getTileId(left, y);
neighbors.push_back(neighborTileId);
}
// right
if (x < mTileColumns - 1)
{
int right = x + 1;
int neighborTileId = getTileId(right, y);
neighbors.push_back(neighborTileId);
}
}
// search the board for the optimal path
void Board::findPath(int startTileId, int endTileId, AIStrategy aiStrategy)
{
std::map<int, int> cameFrom; // neighborTileId, current tileId
std::map<int, int> costSoFar; // total cost so far for the path from startTileId
std::vector<int> neighbors; // vec of the neighboring tileIds
WeightedQueue weightedQueue;
weightedQueue.push(0, startTileId); // Lowest weight item moves to the front of the queue
costSoFar[startTileId] = 0;
cameFrom[startTileId] = startTileId;
while (!weightedQueue.empty())
{
// current tile we are working with
int currentTileId = weightedQueue.get();
// exit if we've reached the goal tile
if (currentTileId == endTileId)
{
break;
}
// get all the neighbors for this position
neighbors.clear();
collectNeighbors(currentTileId, neighbors);
for (int i = 0; i < (int) neighbors.size(); i++)
{
int neighborTileId = neighbors[i];
Tile *neighborTile = mTileMap[neighborTileId];
int totalCost = costSoFar[currentTileId] + neighborTile->getWeight(aiStrategy);
if (!costSoFar.count(neighborTileId) || totalCost < costSoFar[neighborTileId])
{
// if we haven't been here yet, add it to the weightedQueue
weightedQueue.push(neighborTile->getWeight(aiStrategy), neighborTileId);
cameFrom[neighborTileId] = currentTileId;
costSoFar[neighborTileId] = totalCost;
}
}
}
setPath(startTileId, endTileId, aiStrategy, cameFrom);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.