[Development] Pathfinding within bases

Talk about the game
Post Reply
Woetoo
Posts: 70
Joined: Wed Jun 24, 2015 10:40 am

[Development] Pathfinding within bases

Post by Woetoo » Sun Jun 12, 2016 6:01 pm

Background to this post

Firstly, whilst I'm a unemployed programmer of ancient legacy systems, I've no clue about 3D/2D worlds, programming in C++, vector3 objects, OOP, floating point numbers, game development or anything vaguely that could be considered a relevant technical background for this post.

Not that I'm going to let that stop me.


My observations

Yesterday, I played Maia 0.56 for a single play session of about 2 hours. No loading, no restarting. It didn't crash and I built a fairly large base.

But my impression was that the longer the game went on, the less predictable my colonists path finding became.
That's unfair, I wasn't really taking much notice until about the 90 minute mark when I was getting concerned that objects I'd requested be built 85 minutes ago still hadn't been built.
So I started to watch a colonist for 3 or 4 minutes. I think he was drunk and blind and perhaps had a small bar magnet embedded in his head. And I didn't think he was alone.

Now there are a lot of factors that could be the reason. I didn't build any plants. I barely built any lights. There's probably some other psychological reasons why I was being bad to my colonists.
There were a lot of small objects on the floor (ore piles) and the base was much larger that at the beginning of my play session. So there are lots of "working as intended" reasons why my colonist was walking some very obscure routes.
... or the AI was messing up.

I'll be posting a video of my testing session, if it ever finishes processing.


My idea

So I was thinking of one of my favourite games of yore.... Settlers. I think Settlers 3.
In that version of the game, a game NPC walking along a path would create a minor impression in the ground. Not even visible at first.
More NPCs walking along that same path would further impact the world until after a fairly short period of time the grass would be worn away and a minor soil pathway would become visible.
Once (or maybe before) the path became visible, it became the preferred route and slightly faster to travel upon. Which in turn meant more NPCs would choose to walk that way as opposed to on the grass.
NPCs would mainly choose those paths again and the pathways would become roads, etc.

Whilst I don't believe that same system would work in Maia, it got me thinking.

What if once an object is placed in a room, the AI re-calculated a path across the room joining as "shortest path" between two doors. Marking (invisibly) a path along the floor for each path from one side of the room to another. That way, when a colonist needs to get somewhere within the base, they don't need to plan out the whole journey in explicit detail, instead just thinking about a series of connections between rooms via these discrete mini-routes. Then once they reach their intended room, there's still the small matter to getting to the object they want to interact with.
There are complication obviously.
It doesn't address open-world pathing, or plant growth outdoors.
It doesn't address impassable rooms where the player has blocked the way, but "going the long way around" is still possible.
Calculating a route between two doors placed side by side in the same wall seems 99% pointless.
IMPs would need to be instructed to not place anything down that would block one of these routes and pick a different spot with the room if possible.
Players shouldn't be aware of the hidden paths and potentially they might block them - but I think that's a choice the player needs to be able to make and interaction points should sort out the rest.
Then there's the extreme case of a player building a huge room and putting a door into every potential place on every available wall. (So maybe it's not shortest route between doors, maybe it's between walls or rooms?)

I don't know if any of that helps. But it's a thought, and perhaps it might be a positive contribution.

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest