Finding My Way With A*

Finding My Way With A*

Posted by on Jan 27, 2016 in Game Development

Oh boy. The longer I continue with this game development thing, the more I realize I’m nowhere near equipped to do anything about it. Case in point: simulating greater NPC livelihoods through pathfinding.

My current NPC implementation is rudimentary: I have a pool of potential, generic merchants, and there’s a chance they’ll spawn at a jumpgate in a sector that the player is in. They’ll dock at a station, take some goods or leave some goods, and then fly off to another jumpgate and go back to the pool, effectively vanishing from consideration while the background sim moves goods around on their behalf.

Ideally, I want NPC merchants to be the simulated wrench in the player’s works by allowing them to actually “move” through the game world on their own. After buying goods at a station, they’d be able to pick a station to sell at from any in the database that buy those goods, and would “use” the jumpgates to get to their destination. Because the other sectors they’d be traveling through aren’t “online” — i.e. they’re scenes that aren’t technically loaded — it would only be a simulation, but I want the NPC’s trip to be as accurate as possible. One option I considered was to simply “jump” them to their destination, meaning as soon as they left the player’s sight they’d simulate the selling and buying, would “jump” to a new sector, etc. They’d have access to technology that the player didn’t: instant teleportation to anywhere in the universe! Since that’s kind of cheating, and because I’d like to have the player maybe be able to actually follow (and maybe interrupt”) an NPC from gate to gate, I need some kind of pathfinding solution to calculate a route the NPC would expect to take if they had the ability to move from scene to scene.

The Big Name in pathfinding is A*, and that’s where all roads seem to lead me, but A* is built on some specific assumptions that my system doesn’t currently subscribe to. I’m finding that all examples and explanations are presented as a function of contiguous steps, as in a grid of squares or hexes. My map is more spread out, although technically I could illustrate it so that each sector is immediately adjacent to one another, forming a crude tile map. Another issue is that the requirements of the algorithm are based on a weighted metric that’s a factor of A) how far you are from where you started, and B) how far you have left between where you are at any given time, and your intended destination. I don’t have measurements between my sectors, since a jumpgate solves the distance issue by fiat: you’re teleported between connected gates without regard to how far the sectors are in physical space.

So the plan, then, is to lay out the sector map in a grid (on paper). This will only allow each sector to have four possible adjacent sectors, which will require some re-mapping of my current layout. Each gate will have a D value of 1, since moving between any two adjacent sectors is equally cost-efficient thanks to the jumpgates. Using a grid will allow me to pin a Cartesian coordinate to each sector — something I really didn’t want to do from day one — which means I can calculate the (I’ve seen people saying to “estimate” h, but I have no idea how we’re supposed to do that if we don’t know how many sectors we need to pass through…which is part of why we’re doing pathing in the first place!). Since g is an additive value — the cumulative distance from the start — I should have all the parts I need to do these calculations.

Why not use an established A* implementation? Again, this is all simulated. I don’t have a physical anything to work off of. I have a table which contains the jumpgates, their home sectors, their destination sectors, and their destination jumpgate ID’s. That equates to the “map” of the universe, or at least the traversable map of the universe, but it’s all “theoretical”, highly irregular in space, and without measurement between each sector. I’m having to throw in a whole lot of useless, arbitrary data just to get a rudimentary A* system in place, and that doesn’t make me happy, but I am so outclassed in this corner of the project that it’s the only solution I’ve been able to grasp well enough to make a go of it.

The good news is that if I can pull this off, I can also use this algorithm to allow the player to plot routes to known sectors, at which point I might be able to use the Cartesian coordinates to somehow lay out a map of the known universe. The only issue with that would be that I couldn’t represent the sectors as adjacent; they’d have to be displayed with representative distances so the universe doesn’t look like it was designed with a ruler and graph paper.