More on Pathfinding

More on Pathfinding

Posted by on Jan 28, 2016 in Game Development

I should have titled it “Moron Pathfinding”, but self deprecation aside, let’s talk about getting from point A to point B.

I set down some graph paper and translated my rough map of the Universe to a coordinate based structure. In-game, this has absolutely no bearing whatsoever. It doesn’t currently matter where each sector is located in relation to others in terms of how players get around since they can only travel via jumpgates.

But in terms of pathing, it turns out that position and relation matters a great deal. When you’re in a place surrounded by n number of avenues that could lead you to your desired destination, you need to know which avenue to pick. In the real world we have the ability to navigate by direction, since the compass never changes. We also have maps and GPS to help us. In the arbitrary world of a game map, though, we have no intrinsic way to select which exit we should start with. In my case, the fact that the sectors have no concrete relationship to one another in space (!) meant that it was damn near impossible to tell which jumpgate to use to start the journey, and later on which ones to use to continue the journey.

With my trusty graph paper I placed sectors in relation to one another and then used the Cartesian coordinates to ID each sector. I had to add support for this data to the JumpgateDataObject class, and then to the sector editor, and then had to fill out the database itself with the data. I then looked at a C# implementation of A* that I found on Code Project but realized that it would require some serious re-working to get it to play nicely with my implementation, so I opted to just roll my own with this example as a guideline.

The implementation I came up with was this: the measurement between the current sector and the destination was going to be a no-frills Pythagorean sussing out of the distance between those two coordinates. The system would first determine each exit from the current sector. It would need to calculate the distance between the destination sector and each possible exit from the current sector, and then select the shortest distance as the most viable option while discounting the others. The pointer would move to that viable system and repeat the process. This is the “A* for Idiots” explanation as I understand it. The process would continue until one of the exits leads to the destination as the next sector, at which point everything would end and the list of sectors that the system discovered was printed out for review.

Two problems: The first time I tried the process, I miscalculated on each possible exit. I was calculating the distance between the current sector and the next sector, and not the next sector and the destination. This gave rise to issues where it would pick the most convenient exit, but it wouldn’t necessarily lead me in the direction I needed to go. Picking the shortest distance between the potential exit and the destination should lead me in the direction of where I want to go, except when the sector design was broken. Some of my sectors are cul-de-sacs, with only one entrance, and the same exit. When it was determined that one of these dead-ends was the closest sector to the destination, then nothing could happen and the process would die, especially since the process negates the use of sectors we’ve already passed through.

By switching the distance calculation to use the distance between potential next sectors and the destination, and by re-working the map so there are no dead-end sectors, the code worked as expected. I was able to plot routes from one side of the map to the other, theoretically as efficiently as possible. Since I’m not considering the cost between sectors — which would be the calculation of the distance between the current and potential next sectors — the route could be a bit longer than it would be otherwise, but at least I know that my pathing will be moving in the right direction, and not taking the NPC or player into the depths of unknown space.