TeamPorcupine / ProjectPorcupine

Project Porcupine: A Base-Building Game...in Space!
GNU General Public License v3.0
484 stars 277 forks source link

Pathfinding Improvements #1560

Open Geoffrotism opened 8 years ago

Geoffrotism commented 8 years ago

Problem

The current pathfinding system often takes a long time to find a valid path if the distance between starting and ending locations are large.

Suggested Solution

I would suggest switching to JPS (jump-point system) to do all exterior pathfinding. This method has a substantial decrease in evaluation time compared to A* and Dijkstra. One thing to note is that JPS requires uniform movement cost across tiles which is why @vogonistic suggested to use it for tiles in space. We would use A* for tiles inside to make use of the movement cost modifiers.

JPS was originally used for 2D tile graphs that allowed diagonal movement. (you can read a good summary here: http://zerowidth.com/2013/05/05/jump-point-search-explained.html

The problem with this is that we have a 3D map and do not allow diagonal tile movement. I propose that instead of expanding diagonally until finding a forced neighbor, we expand along the X coords and expand along the Y and Z axis when looking for forced neighbors.

My reasoning has a little bit to do with the psychology of the mind. I believe most people are likely to build their space station, it will be more wide than tall. Most players in factorio build their bases spanning horizontally. Disney World in Florida was designed knowing that most people will enter the park and then turn right instead of staying straight (which is why the bridge to futureland is wider than that of the other bridges.)

This will help in the case that the distance (as the crow flies) to reach the X coord of the end point is larger than the distances to either the Y or Z coords.

Task List

koosemose commented 8 years ago

I'm not sure we can absolutely guarantee that just because something is in space it won't have a different movement cost (especially in the future when we start getting planetary surfaces). Honestly the pathfinding isn't that bad when it's actually using A*, rather than having to fallback to djykstra (which it has to do when searching for an inventory to fulfill a job.)

Also, we do allow diagonal movement, but only when it doesn't clip a corner.

vogonistic commented 8 years ago

For JPS I was thinking that we might consider outside a 0G environment and sort tiles into just impassable and passable tiles. Secondary gains is that it's not based on graphs, so we don't have to maintain a graph for outside just to do pathfinding.

I think the biggest bang for the buck would be to make the pathfinding hierarchical (over rooms is my suggestion). This way we can very quickly determine if objects are reachable on a room level and if we start locking doors, we will be able to skip them in a very low cost way.

If we also add a lazy cache between doorways in a room, they will probably have a fairly high cache hit ratio as well as meaning that the pathfinding will only be within the starting room and the ending room, using caches for all rooms between the objectives.

koosemose commented 8 years ago

Perhaps in the future we can mark if a room has gravity or not (and have the traits of the Outside room be settable per world), and use JPS in those scenarios? Which would of course mean these changes wouldn't affect a planet.

I think making use of room graph could also help for finding closest inventory (or furniture), find what room it is in, and then do a simple distance check for how far each inventory of the chosen type is from a given spot (presumably the entrance/exit used, if that information is accessible), and then path to that specific inventory. It wouldn't be perfect, particularly for a large oddly shaped room (such as Outside), but it should do well enough and eliminate or reduce our reliance on Dijkstra for finding closest inventory/furniture.

Geoffrotism commented 8 years ago

-I'd like to make a special note that JPS is miles and above faster than traditional A_. http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf page 5 shows that JPS is 36 times faster on a map from Dragon Age, and _215* times faster on Baulder's gate. In comparison HPA* has at max an improvement of 10x the speed of A* on those same maps.

I'm assuming we will forgo trying to extend diagonal movement into the Z axis then.

So we should just fix the no path bug?

koosemose commented 8 years ago

I intentionally avoided diagonal movement on the Z axis, mainly because the logic for it gets extremely complicated.

vogonistic commented 8 years ago

@Geoffrotism A lot of it has to do with the particular use case though. In our case with a HPA*-ish algorithm, we get access to caching which they aren't using in those tests.

This is an interesting video to watch for people who are interested in JPS: https://www.youtube.com/watch?v=NmM4pv8uQwI

vogonistic commented 8 years ago

@koosemose If we use something like HPA* and there are cached paths between doors, we already have a pretty good idea which inventories are most likely to be closest and could do a direct pathfinding to the top items to see which one is closest. It might not always produce ideal results, but it's bound to be magnitudes faster for the worst cases.

koosemose commented 8 years ago

@vogonistic As much as I could understand of that sounds good.

And I definitely think in the case of pathfinding we can accept not absolutely optimal solutions. Which includes the whole thing I remember you talking about with some folks about... non admissable heuristics... And actually watching quill play rimworld I noticed some of the paths generated seemed to show evidence of just that, like going diagonal for a bit and then another diagonal where optimally it could have just gone straight in the first place, and I don't think I'd have noticed it had I not just before the video been looking up exactly what that does to pathfinding.

NogginBops commented 8 years ago

If we don't already save a list of all inventories I think we could do that and reverse pathfind with A* from the item to the character. That is if we are in open space, if we are in a room then I think that we should use what @vogonistic said. We could go a step further and store all the inventories in a room and use that info to do reverse A* to the character, this would work for the outside aswell.

vogonistic commented 8 years ago

We currently store all inventory based on the inventory type, but we really ought to change the structure to be based on room as well. One thing to keep in mind is that the count might be very high, so I think it's important to try to find a subset that is the most likely to be close that we search to or from. It really doesn't make any difference to me if it's a reversed search or not, I would just focus on maximizing the cache hit ratio.

koosemose commented 8 years ago

Yeah, the most significant issue isn't so much the pathfinding itself, it's finding what item to pathfind to, which is achieved by just doing a dijkstra, which quickly becomes massive once it's not longer contained by floors and walls.

Inventory knows its tile (when it is in a tile) which means it knows it's room so that should work along those lines. Unless you're talking about a room knowing what inventory it has (which it can do, but involves searching all of it's tiles, so probably not the kind of thing we want to do on the fly).

If rooms can be aware of inventory contained in them (without having to search every tile), that would allow us to somewhat narrow down the closest inventory, and then, from those pick a couple closest (by straight distance) to pathfind to, or even just one, and accept that it won't be exact.

vogonistic commented 8 years ago

I don't think it matters if the room knows about it's inventory or if they are stored in such a way that we can just quickly get the inventory for a particular room. One argument for not storing it in the room itself is that it makes it easier for us to break large rooms into subareas and base the inventory and pathfinding on that instead. I haven't decided what I think on that though.

As long as the list of inventory for a room and type is cheap, we can make an hierarchical search where we exclude whole rooms/areas if they don't contain the inventory and only resort to a tile based djikstra when there are more than one item in the first room to contain some. This doesn't guarantee finding the closest item, but if we have the cache, we can use door to door distances and it'd find the closest room that has inventory of the right type and the closest one in there. This'll cut down the amount of tiles we search in the djikstra by a lot.

There are all kinds of other things we could play with too. Like sorting the inventory in that room based on manhattan distance to the door we'd come through and then find the path directly to the first few and take the best.

koosemose commented 8 years ago

I'm not sure how cheap it would be to find the list of inventory for a room with our current system, either checking each tile (which seems not to be a good way), or something along the lines of AllInventory>Where(i => i.Tile.Room == RoomWeWant && i.Type == TypeWeWant)

vogonistic commented 8 years ago

It works until we start having a lot of inventory, but that can be fixed as an optimization later. They are already in a dictionary based on Type, so you just have to check the room.