[13] Pathfinding
12/30/2019, 04:55pm
It was a surprisingly productive morning. I got up a few hours early, and instead of going back to sleep I just hopped on the computer and did what I could to bang out this pathfinding stuff. I fixed a frustrating combat positioning bug that was caused by a badly designed equation and some floating point precision errors. After that, I was able to finish up the pathfinding code and spend some time testing it. Seems to be working well, and I want a break for the evening, so here's the update.
Editor - Tile Walkability Tool
The first thing I did was add a new tool to the editor - the Tile Walkability Tool. I wanted to make it simple for designers to be able to mark tiles as walkable / non-walkable. It's pretty self explanatory, and works like the other tile tools. The editor automatically marks underwater tiles as non-walkable, and I have no plans to add swimming to the game.
When the server starts, the heightmap and walkmap (created with the tile walkability tool) are processed together to generate a final "walkable neighbors" map. This map is then queried during pathfinding - A tile must be walkable as well as have a slope leading to it in order to be traversable. When there are no terrain features in the way, flat tiles can be traversed diagonally.
Pathing
For the actual pathfinding, I'm using the awesome astar crate. And, upon writing this post I realize that this crate is deprecated now. I guess I'll spend some time upgrading it soon.
Getting it working was quick, but optimizing it was a little frustrating. A* pathfinding returns a list of every node along the path, which is fine and makes sense, but I didn't want all that data. I ended up writing a little bit of code to "collapse" the path, essentially giving me the list of nodes that are directly before a direction change. This way, we have the smallest number of nodes that represents the same path, and we have to send way less data over the wire. It also helps to avoid thrashing the movement system, as characters will follow a few large paths between nodes, instead of many tiny paths.
Networking Updates
Today I greatly decreased the number of movement packets that the server sends out per tick, by updating the MovePacket to contain all destinations that an entity has in it's path, instead of just sending the current destination. Now, clients can smoothly move an entity along it's path without needing to stop and wait for a new destination from the server. There is an occasional de-sync, but that is to be expected as I have not implemented any form of reconcilation yet.
Server - 0x04 - MovePacket
network_entity_id: u64 (8 bytes)
dests_len: u64 (8 bytes)
dests: list (? bytes)
x: f32 (4 bytes)
y: f32 (4 bytes)
I also had to update the Movement EntityState. EntityStates are just small bags of data that are sent across the network when an Entity is spawned. Since entities now follow large paths, I had to update this state to include the list of destinations that the entity has yet to reach. Note that in the scenario where a player joins and an entity is halfway through it's path, this entity state will only contain the second half of the path - the newly joined player will see the entity continue it's movement just as the already-connected players would be seeing it.
EntityState::Movement
dests_len: u64 (8 bytes)
dests: list (? bytes)
x: f32 (4 bytes)
y: f32 (4 bytes)
is_moving: bool (1 byte)
That's all for today. Tomorrow, I'll work on equipment and equippable items.
