koobas.hobune.stream
Getting Valid Moves On A Grid
Hey! I have a problem that I'm struggling with for days. I'm currently working on a Turn Based Tactics project, I want to highlight valid moves for a character according to character's movement points (like every other TBS do). I have some of Breadth First Search working but it doesn't return me what I want. I'll provide what my node variables are here. Nodes(which are squares) have all their 8 neighbours listed with them. via this
public List<Node> GetNeighbours(Node node, GridMaster gridMaster) {
neighbours = new List<Node>();
for(int x = -1; x <= 1; x++) {
for(int z = -1; z <= 1; z++) {
if(x == 0 && z == 0) {
} else {
int cx = node.x + x;
int cy = 0;
int cz = node.z + z;
if(cx >= 0 && cx < gridMaster.width && cz >= 0 && cz < gridMaster.depth) {
neighbours.Add(gridMaster.GetNode(cx, cy, cz));
}
}
}
}
return neighbours;
}
in a different class I have a methods like this:
//It's for calculating Vector3 Distance Not for A* Pathfinder.
public int GetDistance(Node nodeA, Node nodeB) {
int retVal = Mathf.Abs(nodeA.x - nodeB.x) + Mathf.Abs(nodeA.z - nodeB.z);
return retVal;
}
//Returns 1 if nodes are neighbours, otherwise returns cost according to distance;
public int GetMovementCost(Node start, Node end) {
if (GetDistance(start, end) == 1) {
return 1;
} else {
int distance = GetDistance(start, end);
int cost = 1;
for (int i = 0; i <= distance; i++) {
cost++;
}
return cost;
}
}
and finally my Breadth First Search implementation is this:
public List<Node> GetPossibleDestinations(Node startNode, int movementPoints) {
Queue<Node> frontier = new Queue<Node>();
List<Node> possibles = new List<Node>();
frontier.Enqueue(startNode);
possibles.Add(startNode);
int cost = 1;
while (frontier.Count > 0) {
Node current = frontier.Dequeue();
for (int i = 0; i <= movementPoints; i++) {
foreach (Node neighbour in current.neighbours) {
cost += GetMovementCost(neighbour, current);
if (cost <= movementPoints) {
if (!possibles.Contains(neighbour) && neighbour != current) {
frontier.Enqueue(neighbour);
possibles.Remove(startNode);
possibles.Add(neighbour);
}
}
}
}
}
return possibles;
}
But in the end all I have is startNodes neighbours, even I raise movement points to 1000. May anyone can help me with that?
public List<Node> GetPossibleDestinations(Node startNode, int movementPoints, GridMaster gridMaster) {
Queue<Node> frontier = new Queue<Node>();
List<Node> possibles = new List<Node>();
frontier.Enqueue(startNode);
possibles.Add(startNode);
int[, , ] cost = new int[gridMaster.width, gridMaster.height, gridMaster.depth];
for (int x = 0; x < gridMaster.width; x++) {
for (int y = 0; y < gridMaster.height; y++) {
for (int z = 0; z < gridMaster.depth; z++) {
cost[x, y, z] = int.MaxValue;
}
}
}
cost[startNode.x, startNode.y, startNode.y] = 0;
while (frontier.Count > 0) {
Node current = frontier.Dequeue();
int c = cost[current.x, current.y, current.z];
foreach (Node neighbour in current.neighbours) {
c += neighbour.MovementCost;
if (c <= movementPoints) {
if (!possibles.Contains(neighbour) && neighbour != current) {
frontier.Enqueue(neighbour);
cost[neighbour.x, neighbour.y, neighbour.z] = c;
possibles.Remove(startNode);
possibles.Add(neighbour);
}
}
}
}
return possibles;
}
That is so far I've achieved. Although its base is working, search is not uniform and tend to go left side. like in these images.
