Deterministic Pathfinding

Unity Engine
1

Hello everyone,
I am currently programming a multiplayer RTS with lockstep. So far everything works fine, but now I am up to pathfinding.

Right now my units don’t have collisions, so they can run through each other and stay on the same spot. I used “SimplePath” and the “A* Pathfinding Project (Free)” for the basic grid-based pathfinding which works very well.

Now I am not sure how to implement collisions in a way, that they are handled on every client the same (deterministic). I don’t trust the physic-collision to get to the same results on every client. Furthermore I want some “advanced” stuff like using a flow-field grid for example. I am well aware of the fact, that I probably have to write my own code for that, but since its a hobby and I want to learn stuff, I am happy to do so.

But now to the main question: What is the basic concept of pathfinding in lockstep-based-games? Does every unit get some squares on the grid and just calculates its way through or do they really “bump” into each other? I mean, on a tile-based game its sort of obvious, but in games like C&C, Age of Empires 2 or Supreme Commander (yay, flow fields!), what “defines” the space a unit needs?

I thought giving each unit a empty entity where it stands on the map, but grid based, so it “jumps” from 1 field to another. this entity gets a unit. which is its representation and “follows” the object, so there are no “jumps” on the screen. This way i can determine where a unit is on every client the same (based on lockstep turns, their duration and its speed). Without collision they never get stuck, and the AI maneuvers the backend-entity so collisions don’t happen, but by code and “thinking ahead”, not just running into eachother.

Or am I just missing something fundamental basic here?

(I hope this is the right subforum here)

2

If somebody knows a good book or two regarding the thematic of “Multiplayer RTS”, I would love to read more about it! All i find is Singleplayer or Turn Based, not Realtime…

3

The A* pathfinding algorithm is deterministic. Floating point calculations aren’t across multiple platforms. If you find a good tut on youtube, you can create a pathfinding implementation that’s float-free.

4

I did published 3 Unity 5.2 UNET real time strategy sample projects here. Are you asking about how to implement AI pathfinding in multiplayer network, or straight up RTS in multiplayer?

If former, I did not use it in my sample projects. However, you are able to use rts_unit_silky_movement project as a stepping stone. You calculate whatever pathfinding you need, and do what the project has done to sync the movements on server and clients.

If latter, you may want to consider playing around with [ClientRpc], [Command], and view the rts_nonplayer sample projects on how to do spawn chaining. It is essential for RTS games.

5

So first off, physics is by it’s nature non deterministic. As far as I know it’s generally not used in RTS games, although I’m not an expert in this area.

Modern RTS games use potential/flow fields to handle pathfinding.

RTS games are niche enough that it’s more difficult to find ready made libraries to handle a lot of stuff. I dug up a fair amount of information while working on pathfinding generally. You just need to start googling you have lot of research to do.