Outpost Universe Forums

Projects & Development => Projects => OutpostHD => Topic started by: leeor_net on June 19, 2020, 12:58:13 PM

Title: Pathfinding Update
Post by: leeor_net on June 19, 2020, 12:58:13 PM
Finally started to make some real progress. The code is still a WIP (can see it as I develop it in the routingFromMines (https://github.com/OutpostUniverse/OPHD/tree/routingFromMines) branch over on GitHub.


So, to explain the image, the line in magenta is the path found from the mine to the nearest smelter. The code is rough and needs some cleanup but it works!

More to come soon.
Title: Re: Pathfinding Update
Post by: Hooman on June 20, 2020, 09:17:44 PM
Oh hey, neat to see some visuals of the progress.
Title: Re: Pathfinding Update
Post by: JetMech1999 on June 21, 2020, 08:23:30 AM
I'll say.  Since I don't understand code, the visual changes definitely give me something to latch on to.  I love seeing something that the original didn't have. 

I do have a question regarding the planetary graphics.  Are they taken from satellite pictures from around our Solar System, with the mining locations superimposed, or are they the result of someone actually creating the graphics from scratch?  The fine detail of craters and mountain ridges look like imported photographs.
Title: Re: Pathfinding Update
Post by: leeor_net on June 21, 2020, 09:39:04 AM
Aside from one I think I'm still borrowing from the original outpost, they're all from public domain images provided by NASA and other government bodies. In some cases I take artistic liberties and make some minor changes to the maps.

The mine's are drawn on top in real time.
Title: Re: Pathfinding Update
Post by: Vagabond on June 21, 2020, 04:41:53 PM
I found cargo routes confusing in the original. Looking forward to seeing this tie together in game.

I've been meaning to try OutpostHD again to see how it has progressed but I keep spending the small amount of time I have for Outpost Universe on Outpost 2 tasks or gameplay.

Title: Re: Pathfinding Update
Post by: leeor_net on June 22, 2020, 10:59:32 AM
That's a common thread. Believe me I get it.

Most of the changes are under the hood -- though there's some stability updates and some gameplay changes, for the most part it's not a huge push forward. Once pathing is fully implemented it'll be easier to see where trucks are and manage resource production a lot better than the 'automatic trucking' that's kind of in there already.
Title: Re: Pathfinding Update
Post by: leeor_net on June 22, 2020, 03:44:58 PM
Further progress:


As before, the lines in magenta are the actual paths found from a mine to an available smelter.


And again after 'dirt roads' were built (just bulldozed paths but still a lot faster than going over unmodified terrain).

Multiple mines finding paths to the available Smelter. Was having some problems with paths not being found between turns after clearing a path and realized that the implementation of the path solver I'm using cache's results so I have to reset between each turn to account for changes to the tilemap.

Anyway, exciting to see it working! Soon-ish I'll have tile highlighting set up so that routes can be seen on the tilemap itself for route management and improvement (e.g., bulldozing paths, building roads, etc).
Title: Re: Pathfinding Update
Post by: Hooman on June 22, 2020, 11:17:13 PM
Oh hey, that's a neat little problem you ran into with the caching. That does raise some interesting questions about when you might need to recalculate paths, and what the cost could potentially be. Cost is probably not a huge concern though, since many real time games are able to handle pathfinding well, so a turn based game should be able to handle it no problem.
Title: Re: Pathfinding Update
Post by: leeor_net on June 23, 2020, 07:20:25 PM
Many real-time games also cache their paths. It makes a lot of sense when you have an environment that isn't changing much. MicroPather automatically clears its cache on its own every now and then -- since the turn-based nature of the game doesn't care about speed for pathfinding I just clear it each time since it can change from turn to turn.

Actually it's why I want to strip out the caching code in MicroPather -- sort of simplify it for the purposes of OutpostHD. Doesn't really need caching there so might as well drop it. BUT, that can be relegated to another time after the intended behavior is implemented. :D
Title: Re: Pathfinding Update
Post by: Goof on June 27, 2020, 05:42:48 AM

I'll put my 2 cents idea.
Keep the cache feature and just reset it when a tube/road is built/destroyed.

If you doesn't build an element that could alter path finding, then the cache is used.
If you build one, then the cache is dropped and computed at the next turn.

Title: Re: Pathfinding Update
Post by: Sirbomber on June 30, 2020, 07:55:03 AM
The problem with that is, since buildings need to be built on bulldozed terrain, that means bulldozed terrain will be created/destroyed pretty much every turn anyways, so you'd still end up having to recalculate routes just as frequently.  This could be mitigated somewhat by only checking if bulldozed tiles making up the route were destroyed/built over, but then there's still the issue of figuring out if a newly bulldozed tile has opened up a faster route.  Obviously, you and I can tell pretty easily that a newly bulldozed tile on the other side of the planet won't make a faster route than the one that already exists, but route calculation would still need to check it anyways, unless there was some other process filtering out tiles that were too far away to be part of a faster route, but that in itself could be pretty complicated to write, and there's always the risk of incorrectly filtering out tiles that actually are part of the shortest route.  At the risk of putting words in leeor's mouth, it might be worth coming back to this in the future, but since there's already a good enough and fast enough solution, I'm guessing it's low priority.
Title: Re: Pathfinding Update
Post by: Arklon on June 30, 2020, 08:48:04 AM
I think the standard way of dealing with sub-optimal paths due to the map changing that problem is to, well, just not deal with it, and the path doesn't get re-optimized unless you do another move command. If an obstacle is encountered, then you have to detect that and recalculate a route, unless you use an algorithm like D* where that's built-in. Writing a pathfinder is always corner case hell all the time.
Title: Re: Pathfinding Update
Post by: leeor_net on July 03, 2020, 02:48:24 PM
I do something like that where I check the path that the mine currently has, check for obstructions and only recalculates a path if the current path is obstructed. I have a feeling I missed something in it (checking for the start/end still being valid). Still a work in progress but it's getting there!

Also, real-life really makes it hard to move forward on a project like this.  :(