Author Topic: Pathfinding Update  (Read 277 times)

Offline leeor_net

  • Administrator
  • Hero Member
  • *****
  • Posts: 2264
    • LairWorks Entertainment
Pathfinding Update
« 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 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.

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4911
Re: Pathfinding Update
« Reply #1 on: June 20, 2020, 09:17:44 PM »
Oh hey, neat to see some visuals of the progress.

Offline JetMech1999

  • Full Member
  • ***
  • Posts: 111
Re: Pathfinding Update
« Reply #2 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.

Offline leeor_net

  • Administrator
  • Hero Member
  • *****
  • Posts: 2264
    • LairWorks Entertainment
Re: Pathfinding Update
« Reply #3 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.

Offline Vagabond

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 986
Re: Pathfinding Update
« Reply #4 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.

-Brett

Offline leeor_net

  • Administrator
  • Hero Member
  • *****
  • Posts: 2264
    • LairWorks Entertainment
Re: Pathfinding Update
« Reply #5 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.

Offline leeor_net

  • Administrator
  • Hero Member
  • *****
  • Posts: 2264
    • LairWorks Entertainment
Re: Pathfinding Update
« Reply #6 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).
« Last Edit: June 22, 2020, 04:03:14 PM by leeor_net »

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4911
Re: Pathfinding Update
« Reply #7 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.

Offline leeor_net

  • Administrator
  • Hero Member
  • *****
  • Posts: 2264
    • LairWorks Entertainment
Re: Pathfinding Update
« Reply #8 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

Offline Goof

  • Jr. Member
  • **
  • Posts: 57
Re: Pathfinding Update
« Reply #9 on: June 27, 2020, 05:42:48 AM »
Hi.

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.

Bye

Offline Sirbomber

  • Hero Member
  • *****
  • Posts: 3209
Re: Pathfinding Update
« Reply #10 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.
"As usual, colonist opinion is split between those who think the plague is a good idea, and those who are dying from it." - Outpost Evening Star

Outpost 2 Coding 101 Tutorials

Offline Arklon

  • Administrator
  • Hero Member
  • *****
  • Posts: 1240
Re: Pathfinding Update
« Reply #11 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.

Offline leeor_net

  • Administrator
  • Hero Member
  • *****
  • Posts: 2264
    • LairWorks Entertainment
Re: Pathfinding Update
« Reply #12 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.  :(