15,918,516 members

Hello.

I have a question regarding an algorithm. This is my code that finds the shortest paths for the king and knight from point A to point B and moves around obstacles on its path.

To be more precise, this part of the code handles checking if a square is free (has a value of -1):

The problem is with the queen, rook and bishop in a scenario where for example the board looks like this

A -1 -1 -1 x -1 -1 B -1

-1.....................

.......................

etc.

When moving with the rook for example the output will be wrong, because the algorithm checks all the moves the rook can make and checks if those squares are occupied or not, so it starts checking from x,y(0,0) and raising the x value

A 1 1 1 x 1 1 B 1

.................

.................

etc.

When the algorithm sees that a square X is already occupied it just checks the next possible move for the rook (x+1) and arrives at the square next to the obstacles

In the end I get a path straight from A1 to B1 although there is an obstacle in between.

I know this may seem hard to understand because I am having difficulty explaining it, but I appreciate any help you can give me with the problem.

I have a question regarding an algorithm. This is my code that finds the shortest paths for the king and knight from point A to point B and moves around obstacles on its path.

C#

public List<Node> aStar(int[,] chessBoard, Tuple<int, int> startXY, Tuple<int, int> endXY, int piece) { // All possible kings movements for this example int[] kingMovementX = { -1 , -1 , -1 , 0 , 0 , 1 , 1 , 1 }; int[] kingMovementY = { 0 , -1 , 1 , 1 , -1 , 1 , 0 , -1 }; var moves = new Tuple<int[] , int[]>(kingMovementX , kingMovementY); // Add first node to open list List<Node> open = new List<Node>(); List<Node> closed = new List<Node>(); List<Node> zero = new List<Node>(); Node currentNode = new Node(startXY); open.Add(currentNode); int newX = 0; int newY = 0; // Adding adjacent nodes to the open list for (int i = 0; i < moves.Item1.Length; i++) { newX = currentNode.Position.Item1 + moves.Item1[i]; newY = currentNode.Position.Item2 + moves.Item2[i]; if (newX >= 0 && newX < chessBoard.GetLength(0) && newY >= 0 && newY < chessBoard.GetLength(1)) { if (chessBoard[newX, newY] == -1) { Tuple<int, int> newPos = new Tuple<int, int>(newX, newY); Node adjacentNode = new Node(newPos, currentNode, 1); open.Add(adjacentNode); } } } // remove starting node from open list and add to closed list closed.Add(open[0]); open.RemoveAt(0); // repeat until the open list is empty or stop with an error while (open.Count != 0) { // selecting the node with the lowest cost from the open list and adding to closed list int lowest = 99; int lowestIndex = 0; for (int i = 0; i < open.Count(); i++) { if (open[i].Cost < lowest) { lowest = open[i].Cost; lowestIndex = i; } } // if target is added to closed list the path is found closed.Add(open[lowestIndex]); if (open[lowestIndex].Position.Item1 == endXY.Item1 && open[lowestIndex].Position.Item2 == endXY.Item2) { return closed; } open.RemoveAt(lowestIndex); // check all adjacent nodes that are not in a closed list and do not have obstacles currentNode = closed.ElementAt(closed.Count - 1); for (int i = 0; i < moves.Item1.Length; i++) { bool isInClosed = false; bool isInOpened = false; newX = currentNode.Position.Item1 + moves.Item1[i]; newY = currentNode.Position.Item2 + moves.Item2[i]; if (newX >= 0 && newX < chessBoard.GetLength(0) && newY >= 0 && newY < chessBoard.GetLength(1)) { if (chessBoard[newX, newY] == -1) { Tuple<int, int> newPos = new Tuple<int, int>(newX, newY); Node adjacentNode = new Node(newPos, currentNode, currentNode.Cost + 1); for (int j = 0; j < closed.Count; j++) { if ((closed[j].Position.Item1 == adjacentNode.Position.Item1) && (closed[j].Position.Item2 == adjacentNode.Position.Item2)) { isInClosed = true; } } // If a node is already in the open list and when the cost of the node // in the open list is larger than the cost of the current node add current // node as a parent to the node in the open list if (isInClosed == false) { for (int x = 0; x < open.Count; x++) { if ((open[x].Position.Item2 == adjacentNode.Position.Item1) && (open[x].Position.Item1 == adjacentNode.Position.Item2)) { isInOpened = true; if (adjacentNode.Cost + 1 < open[x].Cost) { open[x].Parent = adjacentNode; open[x].Cost = adjacentNode.Cost + open[x].Cost; } } } // if a node is not in the open list, add it. if (isInOpened == false) { open.Add(adjacentNode); } } } } } } Console.WriteLine("No path found"); return zero; }

To be more precise, this part of the code handles checking if a square is free (has a value of -1):

C#

// Adding adjacent nodes to the open list for (int i = 0; i < moves.Item1.Length; i++) { newX = currentNode.Position.Item1 + moves.Item1[i]; newY = currentNode.Position.Item2 + moves.Item2[i]; if (newX >= 0 && newX < chessBoard.GetLength(0) && newY >= 0 && newY < chessBoard.GetLength(1)) { if (chessBoard[newX, newY] == -1) { Tuple<int, int> newPos = new Tuple<int, int>(newX, newY); Node adjacentNode = new Node(newPos, currentNode, 1); open.Add(adjacentNode); } } }

The problem is with the queen, rook and bishop in a scenario where for example the board looks like this

A -1 -1 -1 x -1 -1 B -1

-1.....................

.......................

etc.

When moving with the rook for example the output will be wrong, because the algorithm checks all the moves the rook can make and checks if those squares are occupied or not, so it starts checking from x,y(0,0) and raising the x value

A 1 1 1 x 1 1 B 1

.................

.................

etc.

When the algorithm sees that a square X is already occupied it just checks the next possible move for the rook (x+1) and arrives at the square next to the obstacles

In the end I get a path straight from A1 to B1 although there is an obstacle in between.

I know this may seem hard to understand because I am having difficulty explaining it, but I appreciate any help you can give me with the problem.

Comments

SASS_Shooter
22-Jun-12 15:31pm

This sounds like school homework, and we don't do homework here.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900