- Home /
How do I highlight all available paths with Dijkstra's algorithm on a square tile-based map?
I asked this question before, I accepted an answer, because it worked with the variables I tested with, didn't check if it worked when you change them.
Anyway, when I click on a character I want to see how far it can move on a square tile based map, with x amount of movement points that it has got (like Fire Emblem games). 1 movement point allows you to move one tile to the right, left, top or bottom.
Here is my ValidMoves class which should be finding all paths, but I believe it has problems with the movePoints argument and nextMoveCost in the GetValidMoves function
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class ValidMoves : MonoBehaviour
{
public List<Node> validMoves = new List<Node>();
void Start()
{
validMoves.Clear();
//Tiles initialized and startTile is the current Tile
}
public void GetValidMoves(Node startTile, int movePoints)
{
validMoves.Add(startTile);
for (int i = 0; i < startTile.neighbours.Count; i++)
{
if(!GameManager.instance.tileArray[startTile.neighbours[i].x, startTile.neighbours[i].y].GetComponent<ClickableTile>().isWalkable)
continue;
int nextMoveCost = movePoints - (int) GameManager.instance.tileArray[startTile.neighbours[i].x, startTile.neighbours[i].y].GetComponent<ClickableTile>().movementCost;
if (nextMoveCost >= 0 && !validMoves.Contains(startTile.neighbours[i]))
GetValidMoves(startTile.neighbours[i], nextMoveCost);
}
}
public void clearMoves()
{
validMoves.Clear();
}
}
validMoves is a list of my class Node, which contains information about each tile, such as it's position, and a list of the class Node called neighbours (the tiles that are connected to it).
using UnityEngine;
using System.Collections.Generic;
public class Node
{
public List<Node> neighbours;
public int x;
public int y;
public Node()
{
neighbours = new List<Node>();
}
public float DistanceTo(Node n)
{
if(n == null) {
Debug.LogError("WTF?");
}
return Vector2.Distance(
new Vector2(x, y),
new Vector2(n.x, n.y)
);
}
}
GameManager.instance.tileArray is an array of all tiles (GameObject), it's scripts contain the movement cost of the tile (the amount of movePoints needed to walk onto it) and other info. Eventually I will make class Node accessible through the tileArray, but I just haven't gotten around to doing so yet.
The function only works well when the character has either 1 or 2 movement point. When it has more than that, you can see similar patterns and you can notice that not all tiles are being accessed.
Here are some examples:
2 movement points: http://i.imgur.com/o4XrqgI.jpg
3 movement points: http://i.imgur.com/MGX57Qd.jpg
6 movement points: http://i.imgur.com/cyMccSb.jpg
Any help would be appreciated.
Your answer
![](https://koobas.hobune.stream/wayback/20220612034314im_/https://answers.unity.com/themes/thub/images/avi.jpg)