I have created a map using 3 tiles, grass, blocks, and water. I load the data from a file to make it easier on me
Here is a picture of a quick map I loaded
You can see I have a target at the top left. I can move the target with the arrow keys. I am trying to implement the Obstacle Tracing algorithm and I think I am pretty close. To make it easier I only allow the vehicle to travel in N,E,S,W directions. I have a function that calculates the closest node to the target. The program finds the target everytime, except when it has to go around obstacles. I am having troubling coming up with a good getLeftNeighbor algorithm that would work.
Here is the basic for the algorithm I was given
bool Trace(Node start, Node goal)
{
Node n = start;
Node next;
while(true)
{
next = n.getNodeInClosestDirectionToGoal();
if(next == goal)
return true;
while(next.blocked)
next = n.getLeftNeighbor(next);
n=next;
}
return false;
}
bool Enemy::FindPath(int goalX, int goalY)
{
if(currentPosX==currentGoalX && currentPosY==currentGoalY)
{
return true;
//Already at target
}
map->nodes[currentPosX][currentPosY].visited = true;
Direction nextDirection = getClosestDistanceToGoal();
int tmpX, tmpY;
int totalMoves = 0;
tmpX = currentPosX;
tmpY = currentPosY;
switch(nextDirection)
{
case W:
moves[totalMoves] = 0; //Set first move as left;
tmpX--;
totalMoves++;
break;
case N:
moves[totalMoves] = 1; //Set first move as up;
tmpY--;
totalMoves++;
break;
case E:
moves[totalMoves] = 2; //Set first move as right;
tmpX++;
totalMoves++;
break;
case S:
moves[totalMoves] = 3; //Set first move as down;
tmpY++;
totalMoves++;
break;
}
if(map->nodes[tmpY][tmpX].blocked)
{
totalMoves = 0;
if(!map->nodes[currentPosY][currentPosX-1].blocked && !map->nodes[currentPosY][currentPosX-1].visited)
{
//::MessageBox(0, "Collision", "Collision", MB_OK);
moves[totalMoves]=0;
}
else if(!map->nodes[currentPosY+1][currentPosX].blocked && getDirectionNS() == S && !map->nodes[currentPosY+1][currentPosX].visited)
{
moves[totalMoves]=3;
}
else if(!map->nodes[currentPosY-1][currentPosX].blocked && getDirectionNS()==N && !map->nodes[currentPosY-1][currentPosX].visited)
{
moves[totalMoves] = 1;
}
}
return true;
My original idea as you can see in the code is have the vehicle go left, and if that is blocked go down, and if that is blocked go up. See the problem is the vehicle gets stuck on the right side of the water and continously goes up and down. I tried doing some direction tests, but I just can't figure it out.
