Reputation: 37
I am making a bomberman type game. I want to calculate the distance between two points; players can move in four directions. If I am at (0,0) and want to go to (5,5), I can calculate the distance by using the taxicab distance formula ((5-0) + (5-0)) as I can only move horizontal and vertical.
But now I want to implement walls in the game which the player cannot move through.
My current implementation of distance that just uses taxicab formula.
int distanceTo(Position Pos)
{
return (abs(this->x - Pos.x) + abs(this->y - Pos.y));
}
How do I find the distance between two points (x1,y1) and (x2,y2), considering the immovable boxes/walls that come in between?
Upvotes: 0
Views: 122
Reputation: 1170
With the obstacles, you'll need to replace your simple taxicab distance formula with a more sophisticated pathfinding algorithm.
How big is your grid? Dijkstra's algorithm would work for small grids, and A* (a modification of Dijkstra's) for larger ones.
Amit Patel has an excellent resource describing Dijkstra's and A*, as well as implementation details for each. You may view it here.
Upvotes: 1