Tweaking Pathfinding

[synopia]

Name: Pathfinding
Summary: API and algorithms to find paths between two blocks.
Scope: Engine
Current Goal: Implement a proof of concept and develop a nice API for it.
Phase: Implementation
Curator: synopia
Related: wiki
Repository: https://github.com/synopia/Terasology/tree/pathfinder2


Try it
Check out sources, build, run, start a new world with pathfinding mod enabled. Ingame, use F5 to get a "StartBlock" and a "TargetBlock".
Now the pathfinder will find the shortest path between the start block and any target block.


Algorithm concept
What it actually does:

1. Each chunk is preprocessed to extract path relevant blocks and connections between them.
2. Multiple path relevant blocks (adjacent) are combined into regions.
3. Multiple regions are combined into non-overlapping floors.
4. Contour for each floor is constructed (all blocks, that are neighbors of a block of an other floor).

Now we have for each chunk a small number of floors. Floors and path relevant blocks form a graph, with connections between those elements.

The pathfinding itself uses a hierarchical A* algorithm, to find the path in the constructed graph. Hierarchical means, there are (actual) two levels:
a) Find a (local) path in one floor from block B1 to block B2.
b) Find a (global) path from floor F1 to F2.


Done

• Preprocessing chunks and graph construction
  • Find walkable blocks (solid blocks with at least 2 air blocks above)
  • Find regions (small rectangular 2D areas (looking top-down), non overlapping)
  • Find floors (multiple non overlapping regions, that form a flat, walkable area; connected to neighbor floors)
  • Find contour (blocks at the edges of an floor; each of those blocks is connected to each other block of the contour and its path is cached)
• Pathfinding
  • Basic hierarchical A*
  • Currently only operational on two levels (floors and blocks)
  • Contour optimization
  • Path cache

Todo

• Write more automated tests!
• Fix more, upcoming bugs
• Move code from mod to core (maybe only the API should move to core and implementation stays as a mod?)
• Develop a cool API for pathfinding (use callbacks to enable threaded pathfinding behind the API)
• Optimize, optimize, optimize ...

 

[Cervator]

Awesome! Have a contributor badge

Code looks great, and it is in a nice module. Will have to test this when I get a chance. Rather than leave this in the dev portal want us to move it to the Incubator as a feature thread? We need a pathfinding incubator sooner or later and this is the first solid and organized code that fits

 

[Cervator]

Grabbed code to test - realized it used a couple Java 7 features when it didn't run on my piddly old 1.6 install

That's not really a bad thing since multiplayer is on 1.7 anyway so we need to update sometime. Too late for tonight though! Will have to check again soon.

 

[Skaldarnar]

Hey synopia, nice to welcome you here Entering the stage is working code is quite productive I would say

Your path finding attempts may come in handy when generation and simulation cities and villages. I am still not sure how generation should work best. Using some kind of L-System and expand a road network from a central starting point or locating "sweet spots" and connect them with streets... The latter is the one that may use path finding to connect the places with roads build in a "logic" way (we want to reach our goal as fast/cheap/easy as possible).
Keep going and we'll see what the future brings

 

[synopia]

Cervator: I just pushed a Java6 fix.

 

[Cervator]

Alright! Am able to run it and see it work now, very cool. Last time we just had mushroom blocks (or torches? Forgot) marking a path, this time we have numbered steps, neato

I did manage to find a way to lag it out for some odd reason, but that's to be expected I figure. Keep it up!

Did you check out whatever gives the miniions pathfinding abilities? I'm not sure how fancy that gets, or if there are any tricks to be learned from it.

Edit: Oh! Do submit a "mod.txt" with some info in it. "gradlew idea" generates one even in a blank module but it also ends up blank and the module gets discarded from the mod list. Had to edit it a bit to make it activate

 

[synopia]

Ok, just some status updates:

Due to many, many unit tests, I found and fixed some really nasty bugs. With help of YourKit Profiler I tweaked the code for low cpu usage and, if possible, to low memory consumption.

The chunk preparation is very fast (in fact, faster then I expected). On my machine it takes about 1-5ms per chunk, which should be enough for now.
The pathfinding itself can take up to several hundred milliseconds (although in most times it will take less then 10ms). To reduce lagginess, I moved the hole code into its own thread. This raised a number of new topics, but I am pretty sure, everything can be (or has already been) solved.

Currently there is one main bug left. I can reproduce the problem with a new test (that I wrote in train this morning ), so I am very convinced I will solve the problem soon.

Next topic to focus on is the pathfinder API. Here I am experimenting with a system, where you tell the pathfinder all the pathes you are in need for. The pathfinder will then calculate and update those pathes in background and inform you about changes (that happens, when blocks in the world changes). Look for the PathfinderSystem class in my repo, if you are interested in the details.

Also, I would love to play with mobs moving along the paths. I am actually pretty unsure, if miniions' mob implementation fits well enough. Its a bit difficult, to separate the code for moving from the AI code, that tells how and where to move.

Looking for more updates on L&S! I need those animated models :-D

Cervator: Of course I looked into the miniions pathfinder. Its basically a simple A*, which searches the whole space of possible pathes in each request. Such system is simple and works quite good - but only if the path to query is short. It scales very bad (think so, even without exact measures). With my enhanced system, the search graph is drastically reduced to only a few nodes per chunk (depends on the world of course, but in my experiments it seldom reached more then 20 nodes (in a completely flat world, unoptimized A* needs to search 16x16=256 nodes; with my optimizations, only 4 nodes are needed (the corners).

 

[Skaldarnar]

Hey synopia, I had a look at your wiki page article - looks good
I wonder how expensive it would be to run the pre-processing multiple times with different parameters? Currently, you build the search graph for player like characters (2 blocks high, no special climbing, ...). Could you extend the path finding API later to support parameters such as "valid/minimum height", "max. slope/steepness", "min. size/width" and so on? I thought about some 2x2x4 giant, which would need a minimum height of 4, a "path width" of 2 blocks and everywhere 4 blocks to stand on. Moreover, such giant is heavy and lazy, so he can only climb a height difference of 1 at a time... On the other hand we might have little monkeys (1x1x1), which can climb any wall and need just a minimum height of 1 (or even ¹/₂)...
I wouldn't call it a short hand goal, but you might keep that in mind for later enhancements

 

[UberWaffe]

I'm trying to draw up MoSCoW requirements for all incubator threads (First test release, first playable release, full release). In an effort to help the contributors flesh out ideas and importance of features.
Would you like me to do so for this thread?

 

[synopia]

Okay, made some changes to let some minions run along paths through a maze:

Dont wonder, why they are actually running backwards or jumping at each corner. Its just because they can

PR follows after I fixed some issues. Current version is on my github

 

[UberWaffe]

 

[Cervator]

Awesome, synopia ! I posted that one straight to the social outlets

I'm going to guess you generated that maze somehow, another test world to come with the PR? That would be pretty sweet to encapsulate for general game usage too. Me want!

Also, have an architect badge

 

[Linus]

Nice.
Do you use the HPA* algorithm, or have you developed your own method to make A* hierarchical?

 

[SuperSnark]

Hahaha. This is awesome.

We definitely should work a maze into the L&S topography somewhere ...

I can totally see a constantly shifting maze (like in Labyrinth) filled with Rinzors chasing
you down! ; ) Maybe to be fair to a player the maze only recreates itself after a certain point in time ...

 

[synopia]

MazeGenerator: Yes, its auto generated. After I made the video I included an even better version of a mazegen. Currently its part of the pathfinding mod, but may be moved to any place. Since its a simple chunk generator, one can add a maze to their own map generator (at least this should work).

DizzyDragon: Is there a detailed concept of HPA*? Of course, I read many papers about A* and HPA* and many more about completely different topics. But as far as I know, HPA* is a very general algorithm (basically what I wrote in the wiki). So, the implementation and the concrete concepts are developed on my own - but of course I reused ideas from others. If anyone is interested, I may assemble a link list of fitting topics, although it might take some time, since most of this stuff just exists in my head.

Thanks for the architect badge, btw.

 

[Linus]

There is a paper that formally describes HPA* as way to create abstract graphs and how to search them. The approach used in the paper is defining regions, and using the entrance/exit points on the edges of these regions to create an abstract graph. Yes, the description of HPA* is quite general, but there are also other methods of hierarchical search that don't fit the description

I'm currently in the process of finishing my bachelor thesis about combining Theta* with HPA* as a way to do any-angle pathfinding on large maps. Theta* is basicly A* except you skip a predecessor node whenever there exists a trivial path from the predecessor's predecessor to the current node. The cool thing about this is when you do this on the abstract graph, then whenever the path from abstract node A to B is trivial, then you can skip path refinement on all regions between A and B.

So, if for example, in the abstract search phase, you could find a path from region A to B to C. Normally you would have to compute/recall the concrete paths from A to B and then B to C,
If you know that you walk in straight line from A to C, then no further search is necessary on the concrete graph, and you can just return a waypoint to C instead.

I was wondering if it would be possible to do this with the system you created.

Edit (added example).

 

[synopia]

Ok, so its an implementation of the HPA* algorithm

But in my case, the HPA* is almost exactly the same code as for A* (look at HAStar and AStar). The only important difference is in the expand method, which determines the (walkable) neighbors of a given block. For normal A* you simply select all direct neighbors, for HPA* you add blocks further away (the entrances to other regions).

When A* needs to know the exact distance between such a further away entrance, it starts another HP/A* instance and finds the exact (local) path connecting two entrances. Such paths can be cached.

The real mess is finding good entrances between regions.

Your suggestion is to add another check, that skips the local pathfinding, if there is a trivial, straight path. So my question is, how to determine, if a path is trivial without using A*?

Btw, the current implementation (on my repo) needs around 300ms to find a path through a 25 level maze (80x40) and <20ms with path caching. Total path length is ~2500 blocks. Next I will do some experiments with really big mazes :-D

I also did a quick and dirty Swing viewer for the pathfinding, if someone wants to dig deeper into all this stuff
Edit: I attached a screenshot of the Swing viewer. There you can see those red colored blocks, that are the "entrances" between two regions.

 

[Linus]

You can do a line of sight check between two nodes, to check if you can walk in a straight line between them.


More info on Theta*

 

[Cervator]

Bump

On request I've extracted out the legacy mods/pathfinding to a new style repo at Terasology/Pathfinding

synopia - I created a team with you in it that has admin access to that repo, so you should be able to do anything you need. I dropped in a new style module.txt and .gitignore, filling in with what seemed like appropriate values, but of course the code refers to all kinds of outdated stuff and needs an overhaul.

Rather than creating a new module for it you should now be able to use "gradlew fetchModulePathfinding", in a restructure-based workspace

I kept substituting for Gooey (since he still isn't up to speed) and made a Jenkins job plus enabled the GitHub hook to trigger builds. I put this job on a "ModulesPending" view to highlight that it is waiting for refactoring. The job will run the next time something gets pushed to GitHub, and will naturally fail horribly until properly updated first

 

[synopia]

Great, thanks a lot Cervator!

Yesterday I looked into the multiplayer stuff. Amazing work Immortius and all who made this possible

I will fix the mod to work in Jenkins of course. Currently I have some tweaks in my head, to improve the usage of the pathfinder, especially concerning the background thread stuff (use Futures and such). Maybe an even bigger change is necessary, to make pathfinding work in multiplayer. Have some ideas for that, but I need some time to try it out

I keep you updated in this thread.