Map generation and waypoint order issue.

Unity Engine
1

So I have written a map generator based off of a pixel map and various colors defining different block types. As pictured below

Now the map is being generated left to right starting in the bottom left hand corner and going left to right and up all the way to the upper right of the of the map image. The bright pink blocks in the black are waypoints for creating a path. What is happening because the direction the map is processed the waypoints are connected out of order and zigzagging across the play area, rather than following the road. The result is as follows:

I have been trying to figure out what a good way would be to get the waypoints in the correct order either at generation time or after the play area is generated.

Any help would be greatly appreciated because this problem is totally stumping me.

2

Start at the “beginning” and do a breadth-first-search for “path” tiles and “waypoint” tiles only. Consider everything else to be a barrier. You should encounter your waypoints in the correct order.

That assumes that the map you feed into the thing has an unambiguous ordering. A different map might be ambiguous. For example (Assume S = start, W = waypoint, E = end):

XXXSXXX
XWXXWX
XXXXXXX
XXXEXXX

In that map it’s ambiguous whether the left or right waypoint comes first. So as long as you avoid maps like that, the BFS strategy should work fine.

1 Like
3

So your saying the map I have created will never work. The other issue I see is that no matter what I do with that solution is that when a waypoint is on the opposite side of the map it will throw it off still IE

XXXSXXX
WXXXXX
WXXXXW -< this line will create a zigzag no matter what.
XXXXXXE

feel free to correct me if I am wrong but this means that we will be limited in how we can run the path and the above sample pixel map will never ever work?

4

Im not saying that. If you do a breadth-first search on that map considering only “path” snd “waypoint” tiles, you will encounter your waypoints in the correct order.

It’s only when your path has multiple branches or two waypoints at the same distance along the track that you would need a different strategy.

1 Like
5

The problem is your waypoints have no topology information stored. So it does not just depend on the order they are read in. How does a waypoint shall know to which other waypoint it shall connect? Distance? Direction? The order is defined by the road as quasi topology.
If you just have one road you could do a pathfinding (as PraetorBlue suggested) and only allow it to “move” on the road tiles. Another approach would be, just use the road as “waypoints” but it’s 3 tiles thick. Or have a continuous line of waypoints in the middle of the road. So when starting at start you are always connected to the next one.
Since the waypoints are always in the “curves” of the road (if you can guarantee that) you could also check in which direction the road travels by checking from start or a waypoint 2 tiles in each direction if it is a road tile too. Then just travel in said direction until you hit a waypoint. Kind of a “simplified” pathfinding.

1 Like
6

Ok so this has given me some good places to look. For one I believe I need to separate the map generator and path generator scripts so they are each their own script.Then I can better organize my code for breadth search in correlation to with the waypoint placement.
I will create another color block on the map for the start and finish points so when the map generates I can place the first waypoint and declare it start and same for the end. Then I will use the breadth search to find each node in succession by following just the road until it hits the next way point.
I may be conflating a couple things but I see it my head now that you guys have pointed me in the right direction.

7

Another idea which comes to me is that you could use the color to define the order of waypoints. For example your startpoint is red 255,0,0, the next one has a lower red value 254,0,0 and so on. The last one is your endpoint/goal. This makes image generation for your map more difficult but would leave the order of waypoints in the hand of the map designer instead of an automatic algorithm. With all positive and negative consequences. Just something for your consideration.
You could any color for this (white, greyscale etc). And you can reverse it to define order (start with red 125 and increase it by 1).
But this method makes it pretty difficult to change the order afterwards as you have to change all subsequent waypoints too. So wether it’s worth it depends highly on your workflow how you create the map images and how often they need to change.

1 Like
8

If I use BFS and attack it that way, could I use a layer or tag to control where the search ran through? That way it doesn’t deviate from the road or do I need to manually check each adjacent block to make sure I am staying on the road?

9

My understanding is that you’re reading this thing in as an image file. From there I would probably convert the pixel colors based on a predefined mapping into an internal data structure. I’d probably create a Tile class or struct that contains the type of the tile. For a map like this you can use either a 2D array or an adjacency list to represent the data.

From there you do the BFS, and when you’re at the stage where you would add your neighbors to the fringe queue, just ignore anything that is not a path or a waypoint. for example take this BFS pseudocode from wikipedia:

procedure BFS(G, root) is
    let Q be a queue
    label root as discovered
    Q.enqueue(root)
    while Q is not empty do
        v := Q.dequeue()
        if v is the goal then
            return v
        for all edges from v to w in G.adjacentEdges(v) do
            if w is not labeled as discovered then
                label w as discovered
                Q.enqueue(w)

Inside the for loop on line 9, you could simply skip any edges/neighbors that are not path tiles or waypoint tiles.