Path finding algorithm used to find all reachable points

[Lucid Dream]

Hey, sorry I do not know where I should ask ONI developers my question.

I am curious and would like to know about your path finding algorithm used to find all reachable/unreachable tasks.

Is it bfs or floodfill? Because if it is A*, in my mind, It should run for each pair (dupe, task position).

For example, every time a task is added or removed or the world changes, it should run the path finding algorithm again to update reachable/unreachable tasks.

Also, it there any multi threading?

Appreciated.

[MinhPham]

Each dupe have a navigation map which is their reachable paths, generated using something like Hierarchical path finding, and their navigation map only updated when you make changes to the game map that can affect their navigation path. If you play the game long enough, with a large base and lots of dupes you will notice that every time you build or deconstruct some tiles, or just digging ... some weird things happen like some dupes just stopped for a while before move on to their next thing, that because the game need time to recompute dupes navigation map.

To check if a dupe can do a task, or can pickup somethings is just simple : check their navigation map

[Lucid Dream]

Thanks dude, so, each dupe uses their navigation map to find reachable/unreachable points and if they want to move towards one of them (a task), it uses A* to find the shortest path?

To get a navigation map, the simplest way is to use floodfill or bfs? and to update it, the navigation map generates entirely from scratch?

[MinhPham]

The game is written in C#, so ... if you really want to understand how the path finding work, just go ahead and decompile them (they aren't every complicate but at least they ARE complicate to me ).

Otherwise here's my sum up on how it works :

 - Path finding doesn't need to work with 2D map, instead you can throw at them a list of nodes, and every nodes have some links to other nodes.

 - The map is split into multiple smaller squares called partition, to generate nodes inside the partition they just need to do something like this (since there isn't a start point and an end point ) :

    for (int y1 = y; y1 < y + height; ++y1)
    {
      for (int x1 = x; x1 < x + width; ++x1)
      {
		//Blah blah ...
	  }
    }

 - The path finding part i believe is A* cuz they are good overral, (but whatever algo is fine, they only need to run on small partitions instead of the entire map) ...

 - The game is managed entirely by Unity, with everything is an object (that included the partitions too) that have their Update() function called every frame. For me it's hard to tell if the game is single-threaded or multi-threaded.

Bonus : a path finding comparision (not by me)

 

[Lucid Dream]

LOL, yes, I had decompiled it before but there are many classes and I am lazy

It is logical to use hierarchical path planning. There are a bunch of techniques, RSR, JPS (Jump point search) and so on but I think HPA* is common.

[Mastermindx]

If A* is used, it's not used for everything.  A* is pretty good when you know the destination.  But if you need to get to, lets say, the closest source of iron, the destination is not known and as such, you need to use a different algorithm.

[gabberworld]

in general using a int for pathfind is huge waste of memory, but i guess you to need todo sometimes sacrifice if you want less asm instructions.

let say this is your pathfind map inside pc memory, 0 means its clean , there is no obstacle, that is full game map size what player/developer choose before game start

because all tiles are equal then by default you not need use for tile game the coordinates where wall is located.

one byte can hold the 255 different elements,  walls, water or whatever you name it

and this how should look the pathfind  map inside memory when there are objects

02 = stairs

01 = wall

03 = door

FF - dupe

simple algorithm may not work here

because dupe self is 2 tiles then game does also need look 2 memory location if there is obstacle or not.

note: those are not oni stuff