Unity Pathfinding across Map

Unity Engine
1

I don’t know exactly how to explain this, but, I’m attempting to make a game where a user controls a nation. The game basically consists of a map, which consists of nations, which all control different provinces, which are defined in a bmp file where each is represented by a different color, (here is a screenshot of part of the file, I could not send the whole thing as it was too big)

5418432--550740--upload_2020-1-28_18-18-34.png
5418432--550740--upload_2020-1-28_18-18-34.png640×682 61.7 KB

One of the primary game functions is soldiers, which can be moved across these provinces and used to occupy enemy territory or preform other similar tasks. For these soldiers to be able to move across this map, I need them to be able to find a path to the target province. I have not experimented much with path finding before, but from what I understand a path finding algorithm like A* or Dijkstra’s Algorithm would be what I need to use, and that these algorithms require nodes, representing the locations, and connections to function. The nodes would then, in this case, have to be somewhere in the province near the center, and as I found this to be rather too complicated to produce using C#, I made another map (here is a screenshot of part of that one) 5418432--550743--upload_2020-1-28_18-23-39.png, where the nodes are represented by black pixels, and I plan on creating a script that checks which pixels are black and set these to nodes. From here, the only thing left for me would be connections. I now require a way to determine connections, and I honestly have how I would do this. I would greatly appreciate if anyone could present to me a solution, and thank you in advance!

2

An easy solution would be,
Your structure/class should be like this:

public class sMapZone
{
   public Vector2 position;

   public Player player;//who is in control of this zone

   public int color;//or you can just calculate the color

   public sMapZone neighbors;

   //other vars and methods
}

Now the easiest and not the best way to do it is by counting with a recursive method the steps to make the movement. Save the best path and at the end you’ll have the result. (hard way to find the path, NOT THE BEST with big maps). On your case will take, like 50ms to find the path.

The best way, is to code a A* algorithm (there are tons of examples/tutorials).
Look at these: Pathfinding Algorithms in C# - CodeProject
Implementation of A*

3

So it sounds like your problem currently isn’t the pahtfinding algorithm, because you’re not there yet.

But rather the node problem.

From this:

You seem to want to programmatically determine the nodes by analyzing the BMP file in code. Which is going to be difficult depending on your requirements.

The black dot ones should be easiest as it just requires scanning all pixels and finding those that are black. Problems arise if your BMP has clusters of black pixels rather than just a single one (so you’ll have to filter out neighbour pixels), and if you don’t use pure black and so you have to have a colour tolerance. Then of course you have to translate the pixel location to world space.

Moving on to the coloured map. You’re problem then becomes having to find ALL the pixels of a single colour and finding the center of it. That’s going to get a bit more complicated since the shapes are organic and potentially concave. And we also have the problem of colour consistency. Is there a guarantee each region is the SAME colour to the bit? And of course the pixel location to world space problem.

You could go into Photoshop (or gimp, or whatever), create 2 layers. One for the map, and one for the node centers. Put black specs on the node center layer and export that as one image, and the map layer as another image. And then you feed both of those into your map code and rely on the simpler logic of the first… if you master that.

Or you could just manually place them in Unity by importing the bitmap into a prefab, then drop GameObjects in the center of each region, and using those as nodes. Resolving all of this, so you can then move on to the A*/Dijkstra portion of the problem.

4

Yes, I have done this, and already have made code that makes it so that the black pixels are turned into “nodes”. The colors are consistent, it was generated and I have already checked this. The issue is that I need to work on connections. I need to make it so that not all nodes are connected, but instead only the nodes that I need. For that to work, I am planning on using the province map, and I need help figuring out how to do that.

5

Unless you plan on drawing tons of maps, and you need some import pipeline to set everything up for you repeatedly.

I still think manually setting it up with be easier.

6

I could do it manually, but there are lots of provinces and I feel that would take too long. Right now I’m attempting to find a way that, when it finds a black node, it checks for the province it’s on, and then determines it’s neighbors, but I don’t know how that’ll work.

7

Like I said… if this is for a single map. You probably have already spent more time pondering the question by now than if you had manually done it.

You have a lot of geometric issues… like in the black dot situation. Well… those black dots actually correspond to a colour region. The “neighbours” is determined by that. With only the black dots, the only information you have is proximity from center of region. But when you look at the colour map, there’s more to if they’re neighbours. You need to know if their boundaries bump up to one another. You need to know more information than proximity, there’s extra information missing.

Like take this elongated country in greenish yellow:
5422923--551493--upload_2020-1-29_19-12-13.png

it’s center is between the pink and tealish? colour regions. Thing is it neighbours that pail green all the way on the left. But if you drew ONLY black dots, it would look like that greenish one doesn’t and that the teal and brown ones are it’s only neighbours on its west side. Unless you extened proximity range… but then if you did that, it might think that whitish on in the center left is its neighbour, or that pail green in the center middle.

And analyzing the colour map in code… well, it’s non-trivial. Sure we could get into teaching you how… or you could even hunt down a library that MIGHT actually have already implemented this exact case for you… or find an image analyzing library that gives you some rudimentary data back that could be further broken up into the information you need.

But all of that is going to take time.

Time that is likely longer than if you just drew the map and set it up yourself. We’re talking… an hour maybe?

If you don’t want to take that time… well. Maybe someone else will be able to come along and assist you. Cause I don’t necessarily want to take the time to explain how to write some code that will filter out a bitmap by colour, create a graph from it, and find the connecting edges to each vert. As well as get a full in depth explanation of the image from you (like what are these dark coloured regions… should they be ignored?), as well as debugging out issues that might arise from assumptions made due to lack of explanation (like consistency of colour across a region in the bitmap, or other noise in the bitmap, especially if it’s actually a compressed image), so that I could effectively explain how, nevermind getting into understanding your base line understanding of it. Cause now it’s not just your time, but our time.

TLDR;

Sometimes it takes longer trying to solve a problem that could have been resolved with a much shorter and simpler brute force manual approach. It’s like building a contraption to dig a hole to install your mailbox… if you only have 1 to install, it might just be easier to dig the hole by hand.

8

So, how would you suggest I do this manually? I’m assuming that I don’t assign each of these nodes neighboring nodes, but instead it seems I would make some sort of map. How exactly would that work?

9

There’s lots of ways.

Easiest would be open up Unity, add the visualization of the map to a GameObject.

Now, create child GameObjects of that and place them at each position at the center of each region (like the black dots).

Next create a script that has a “neighbours” array on it (make the array the type of this script… you could use a list as well). Attach that script to all of the nodes. And then for each node, in its inspector, drag a reference to each of its neighbours.

Done…

NOW, when you write your A*/Dijkstra or whatever. You just get all the nodes (you could easily just GetComponentsInChildren of the map). And any time in your algorithm you do a “GetNeighbours” call (when you research A*/Dijsktra, this will make sense), the array/list on the script are those neighbours.

1 Like
10

cont’d

Personally when I wrote my A* and Dijkstra, I did it in an abstracted manner.

A*:

Dijkstra:

They take in a IGraph:

You could then implement as follows:

public class MapNode : MonoBehaviour
{

    public List<MapNode> neighbours;

}

//attach this to the map, where the MapNodes are all children
public class Map : MonoBehaviour, IGraph<MapNode>
{

    [System.NonSerialized]
    private MapNode[] _children;
 
    void Start()
    {
        _children = this.GetComponentsInChildren<MapNode>();
    }
 
    public int Count { get { return _children != null ? _children.Length : 0; } }
 
    public IEnumerable<MapNode> GetNeighbours(MapNode node)
    {
        return node.neighbours.ToArray();
    }
 
    public int GetNeighbours(MapNode node, ICollection<MapNode> buffer)
    {
        //the point of this method is to b e like GetNeighbours but with less garbage
        foreach(var n in node.neighbours)
        {
            buffer.Add(n);
        }
        return node.neighbours.Count;
    }
 
    public bool Contains(MapNode node)
    {
        return _children != null && Array.IndexOf(_children, node) >= 0;
    }
 
}

And now Map can be passed into the A* or Dijkstra resolver and get a path back.

Like so:

var resolver = new AStarPathResolver(mymap, ComponentHeuristic<MapNode>.Default);
resolver.Start = someStartNode;
resolver.Goal = someEndNode;
var path = new List<MapNode>();
resolver.Reduce(path);
11

Thank you!

12

What exactly is the IGraph? I looked it up and all that came up was part of shader graph.

13

… it’s part of my library, I included a link to the source.
It’s an interface.

I wasn’t really giving it to you as a “do this”, but rather as a “here’s a general idea of how things are done”.

Like I’ve said, things take time, this isn’t trivial.

14

yeah, I just couldn’t understand that part of the code, that’s all

15

So, IGraph:

Is an interface that represents a “graph”. In graph theory, you have what is called a ‘graph’ made up of verts and edges (nodes and paths to neighbourhing nodes). A* is an algorithm that based on some graph, it can find a path from one node to another through the graph.

You can think of a “graph” as synonymous with “map of nodes with connections”.

In my implementation of A*, I made sure to abstract the concept of a “graph” away from the concept of the pathfinding algorithm. This way you can implement the IGraph interface, pass it into the algorithm, and it’ll just work. My the graph be a grid (like a checker board), or a hex grid, or a loose node graph (like your map), or any other kind of graph out there.

I also abstract out the heuristic (the estimation of distance between nodes) for a similar reason.

So that’s what an ‘IGraph’ is. It’s just the interface that defines the abstraction layer between the A*/Dijkstra algorithm and the “graph” it acts upon. If you look in the A* class I posted it has no concern over how the “graph” is layed out… it only cares about “get neighbours of current node” via the “GetNeighbours” method.

16

Ok, that makes sense, thank you. Now I seem to be having another issue, I have the neighbors system set up now, but I seem to be having another issue, A* and Dijkstra rely on distance to figure out the costs of nodes, which they use to determine the next node to search right? So how do I determine these distances?