Outpost Universe Forums

Projects & Development => Projects => OutpostHD => Topic started by: leeor_net on November 24, 2019, 11:53:25 PM

Title: OutpostHD v0.8.0 Preview #1
Post by: leeor_net on November 24, 2019, 11:53:25 PM
Hey all!

I know it's been awhile since I did any development work on OutpostHD. Some of you know what's up, I outlined it a bit in a previous post. Anyway, I'm getting back into the development groove and have made some progress with getting pathing implemented.

I used MicroPather (https://github.com/leethomason/MicroPather) as the A* implementation and so far I'm very happy with its performance.


This is a path that was generated for this surface using Impassable Terrain as truly impassable as well as any tiles that are occupied with a Thing (robot, structure, etc). Will make exceptions for Thing's in the future when Roads are implemented (half cost for traversal). Travel can only happen in four directions (no diagonal movement, just N/E/S/W movement).

Anyway, it's a start! Need to find an efficient way of drawing paths versus just iterating over the list of nodes and drawing a pixel. Probably will just generate a new texture and draw on that and only update that as needed.... but that's implementation details that can be addressed later.
Title: Re: OutpostHD v0.8.0 Preview #1
Post by: Hooman on November 25, 2019, 06:06:39 PM
Hey, that's a neat little map.

I like that you're using external code to get the job done. I don't normally go thinking to use external code. Not unless it's part of a standard library, or at least a massively popular library. I kind of need to work on that, and start searching for what's out there before implementing stuff.
Title: Re: OutpostHD v0.8.0 Preview #1
Post by: leeor_net on November 25, 2019, 08:14:00 PM
There's a shocking amount of very useful code out there that does a lot of things really well. MicroPather is old, but it's well tested and very mature. It's also a lot faster than I expected it to be. Probably wouldn't be able to run the solver every frame even with the built-in caching but it's definitely very effective.

It's why I tend to not roll my own when it comes to well known problem domains -- e.g., XML -- why write my own when I can use a library like TinyXML? Same deal with JSON, YAML, etc. SDL is a great example of this as well -- why deal with the specifics of each platform when I can just use SDL and have my code work with very little change between platforms? I mean, I could roll my own, but it saves a lot of time to use already established code. :D

Would have been great if I knew of a depth-first/breadth-first solver that's general enough to be implemented like MicroPather -- I rolled my own and it was buggy until Sirbomber took a crack at fixing it (and succeeded).
Title: Re: OutpostHD v0.8.0 Preview #1
Post by: Hooman on November 25, 2019, 11:48:39 PM
Fun fact, if you replace the metric function used by A* to something that just returns a constant value, the behaviour degrades to breadth-first search.  :)

A* is kind of like an intelligent breadth-first search, in that by using an estimate of the likely distance, it can expand preferentially in specific direction that is likely to contain the shortest path. When such a path exists, it avoids wasting time expanding nodes in directions that move away from the goal.
Title: Re: OutpostHD v0.8.0 Preview #1
Post by: leeor_net on November 26, 2019, 08:44:23 AM
Pretty much. That occurred to me not long after learning about A* and how the algorithm generally works. I used a depth-first search to determine connectedness in the colony structure so the scope is somewhat limited versus the application of the A* algorithm which is intended to find a path pretty much entirely on the surface. I suppose the biggest difference is that one is check adjacent nodes without a specific end goal with a finite and definite result versus the map traversal which has a start and a determined end point but an unknown possible solution that may or may not exist.
Title: Re: OutpostHD v0.8.0 Preview #1
Post by: Hooman on November 27, 2019, 05:14:49 AM
Exactly. In the case of connectedness, you have to traverse all paths. You're looking for a global property of which objects connect to each other. Any particular path becomes irrelevant in that case, and so there is no weighting of paths or distance/weight estimates.

For pathfinding with A*, there may be multiple paths, and there may even be multiple paths with the same minimum distance. You don't really care about alternate paths though. You just want one path of minimum distance between two specific points. In that case, it makes sense to end early once you have a path of minimum distance.

As a fun little aside, the proof that A* returns a path of minimal distance depends on a property of the heuristic function that estimates remaining distance. The heuristic function must be admissible, which basically means it needs to be optimistic about the remaining distance, or rather, than it never overestimates the remaining distance. If you choose a pessimistic heuristic function which overestimates the remaining distance, A* can return a path which is not optimal, since it doesn't prioritize searching in the direction of an overestimated distance, and so might not find a path which is actually shorter than the estimate. In that case, A* is still able to find a path when a path exists (just maybe not an optimal one), and correctly determine when no path exists.