On Pathfinding (1)

My Previous Solution

I think the best place to start is what I did with the previous incarnation of ‘Bug. At its most basic the actors used a straightforward locally-generated A* path each timestep they were required to moved. They would calculate the entire path, and then move one step but caching the remainder. A quick check a the next timestep would reveal if the path had been spoiled by any changes, and if that meant an immediate collision then the path was recalculated.

Additionally, the actors had a ‘swap mechanic’. This prevented excessive recalculating of pathing by only slightly weighting occupied locations. Ultimately it lead to interesting properties where some actors ganging up on another might split up and take two paths around a column or hallway if it would be more effective.

Finally, all of this was only run if they could perceive their target via any of the sense components they possessed. This led to a complex set of interactions in their decision making systems that ended up being very awkward and landed me right back in the exponentially expanding code problem.

There were myriad other problems with this system:

• Exponentially slower per actor.
• Off screen locations computed arbitrarily.
• Perception mechanics became awkward, and really quite vestigial.
• Additionally, perception mechanics stacked computationally, to the delight of my CPU.

Contemplating The Problem

Since I’ve started anew thinking about the game as a simulation, I’m also rethinking how things will ‘path’ instead of just throwing classic solutions at it. Like any good programmer though, I did start by just throwing classic solutions at the problem.

Before I really committed to the Artificial Life model of thinking about it as a complex whole, I first thought about simply speeding up the model. This led me to moving from A* to Jump Point Search, a (sometimes) faster A* variant. JPS is faster in my case -> small, compact complex room layouts. I would however run into similar problems as before, even with the computational speedup, so I started down the road of more communicative pathfinding.

The world of Robotics uses systems to automate hundreds of real world models, so even with the stress of uniform grids I should be able to as well. This lead me to the world of Multi-Agent Pathfinding (MAPF) solutions. There are quite a few emerging constructs in this realm. Conflict-Based Search (CBS) is an older paradigm that still holds value wherein each actor paths and then the paths are all crosschecked to find conflicts. These conflicts are then recursively resolved per discrete timestep until an overall solution is found that supports all motion for all actors. This can end up being pretty slow, and has been incrementally improved on over the last few years. Symmetry based solutions as well as uncertainty or probability systems allow for constraint based conflict resolution. (This is all very interesting and exciting research, and I implore you to go learn about it!)

The real question slowly formed in my mind -> “What do I want to accomplish?” I kept coming back to how it all felt like ‘cheating’. This is a term I bounce around in my head a ton. How do I path? I don’t tap into some all-knowing conflict-resolving machine, and yet I manage to get from point to point with measurable success. If I need to get somewhere I haven’t been, I either prime myself with information from an external source, or I explore my given environment based on prior expectations. So, what different disciplines require discrete communicating actors? How do I get back to that single timestep solution, without cheating and calculating hyper efficient paths? These questions led me down a road to radically rethinking the scope and style of not just pathfinding, but all the systems of Protobug. I won’t slide into a tangential topic here, but know that I’ve got several other articles in the works surrounding my ideas.

The Current Model

Ultimately it looks like I won’t use discrete pathing, that is, from actor to goal in the usual sense. I also won’t be using any distributed computation with any omniscient construct (MAPF etc.) What it seems like I want to be able to do is generally forgo finding “complete solutions” and instead only solve for a single timestep at a time. The issue of course is I need my actors to not only solve for individual timesteps, but manage get to where they want to go. This leads to other, bigger problems of perception and experiential memory (I’ve already started addressing these) but for now it looks like I will go with a set of pre-calculated (update as needed) flow fields unique to each “room”.

Additionally, this indicates actors will have to communicate in some time-independent sense, to “look ahead” solving collision or symmetry issues in advance. I do have a few notions as to how I might handle this, but it referentially loops back to the experiential memory question. In any event I’ll treat the larger space (complete map of the world) as a giant recursive A* problem. At the highest layer each screen will be a node. One layer below that each room will be a node in the screens graph. Finally each room will feature a flow field to each other adjacent room.

Essentially, if an actor remembers or is told where some desired goal is it will also remember (or be passed) the node graph solution to that goal. At this point it takes one move inside the flow field each timestep, communicating where possible to avoid collision or excessive delay. It continues this along the two higher order node graphs until it reaches its goal. This is a very rough approximation of what I’m working on, and doesn’t take into account the method of reconstruction I’m working on. More on that soon!

As presented, this concept works only in the case of static goals. Dynamic goals should work the similarly, but will require that the actor poll other agents or actors for the goal‘s current location in some ongoing manner.

Next Steps

The next step is to look into the world of fast flow field (vector field, flow graph, etc.) calculation. I could just go with Dijkstra’s Algorithm (or Breadth-First-Search) or some Wave Propagation style field generator. I want the fields to pre-calculated, but to have the ability to recalculate at runtime if I need – basically just for flexibility. I think it’s worth looking into what the world has to offer on this subject before I make any decisions. I’ll write about what I come up with soon.

Thank you for reading!

Communication between Agents/Actors

CBS, MAPF and MAPF Improvements

Classic Conflict Based Search

Multi-Agent non-Overlapping Pathfinding with
Monte-Carlo Tree Search

A* Improvement with Jump Point Search

Visual Representation of JPS