THE DISCREPANCY PATHFINDER

A theoretical (no code given) journal about the process I took in developing the pathfinder module for Discrepancy

  • Gibmaker
  • 11/30/2010 02:20 AM
  • 1985 views
This is less an instructional article than a journal about the process I took when designing the pathfinding module for my game Discrepancy. There is no code given in this article, just a description of the behaviour and limitations of the pathfinding system that was developed. It will probably be of more interest to people who like to program as a hobby, as opposed to people looking for a pre-made pathfinding script for their own games.

Sorry the illustrations are really crude. This is because I made them in Microsoft Paint on a laptop without a mouse.

What? A Pathfinder?

The first question in any programming project is, of course, why do I need a pathfinding module at all?

In Discrepancy, the player never has direct control over characters. The player instead chooses various commands from a menu and the character automatically walks to the appropriate object in the room and uses it. Since the movement routes involved would be for the most part very small, on the order of eight steps or less, I originally planned to manually program each one of them.

But as the maps increased in number, and as the number and types of objects in each room became more complex, the sheer number of movement routes exploded to a prohibitive degree. A single map came to require at least 150 seperate move routes, and there are going to be in excess of 200 maps with this game. I started wanting to scale back other aspects of the game out of exhaustion at having to program move routes to support it all. I started to despair for the emptiness of my life while slugging through this endless slough of move routes. (That's not an exaggeration at all, as Jake Springhorn knows from my many angst-ridden chats during this time.)

So, even though it took a week to create, building a pathfinding module was ultimately a more efficient use of my time. (Speaking about a game that's been in development for two years, so far.) And let's face it, a programming challenge is much more fun than tediously plugging in route after route until I kill myself.

Parameters

The most thorough pathfinding script would consider every single possible series of moves around the map, then simply choose the one that arrives at the destination in the least number of steps. This would be far too time-consuming to execute in a game, though, so measures have to be taken to streamline the method by which a path is found.

The steps I took to this end are particular to Discrepancy's style of play.

- Unlike many RPGs, the player has no direct control over the movement of any character. Instead, the player uses a menu to choose a task to perform in the room, and the character automatically walks to the appropriate object, then returns to his starting place. (Characters ALWAYS return to their starting place after finishing an action.)

- The relative positions of objects in any room is actually completely irrelevant to gameplay. I.E., a roll-to-hit with a weapon will be the same no matter where the characters involved are represented on the screen. Hence, there is no advantage to creating a room with complicated geometry, and maps can be optimized to make objects more accessible to each other if necessary, without affecting the difficulty of the game.

- All maps in Discrepancy are 22 x 18 tiles -- just large enough to fill the screen, with a "gutter" around the outside for characters to step into or out of when leaving or entering a room. And in fact, the "useful" part of a map is even smaller due to part of the screen being covered by the command menu. Thus, we are usually dealing with a very small amount of terrain when finding paths.

- Characters in this game can step diagonally.

The Standard Move

The time I initially spent programming routes by hand did pay off in one respect, in that I noticed a certain pattern to most of the routes in this game. Almost every path needed in Discrepancy consists of a series of steps in a single direction, with a "jog" at some point in a second direction, 45-degrees off. The jog can happen at the beginning, end, or in the middle of the route, and it can be any number of steps. Think of the jog as a "correction" to the position of the mover, so that it is correctly lined up with its destination when it continues moving in its original direction. However, this does not mean that the jog must constitute only a small part of the overall movement, as shown in these examples:



I call this kind of route a "standard move." Evidently, this kind of route is quite versatile at avoiding simple sets of obstacles.



Note that I modified RM's passability checks to allow diagonal steps "around" impassable tiles (evident in all three examples) and "between" two impassable tiles whose corners touch (as in example C). By default, this type of step would not pass a passability check.

The main advantage of using this kind of route is that, while the pathfinder does fall back on the inefficient method of sequencially checking routes for blockages (I'm not smart enough to come up with anything better), we have at least greatly pared down the number of routes that will be checked, with a good degree of confidence that one of them will be valid.

Executing the Standard Move



By comparing co-ordinates of the start and destination points, the program determines which general direction the target lies in and which two of the eight possible directions of movement will be used to approach it.



Destinations that lie in line with the starting point default arbitrarily into one of the regions bordering the line.

In the example, the target can be approached by a combination of East and North-East steps.



There are two possible patterns of movement to reach the destination, based on whether East or North-East is the principle direction of movement, and which direction constitutes the direction of the "jog" in the middle. For this game, I prioritized cardinal directions (ie. not diagonal) to be the principle direction whenever possible, since it makes the movement more sensible considering that RM sprites can only face in cardinal directions (barring extra programming and spriting that I didn't think would contribute much to this game) and I also prioritized that the jog should happen as early as possible in a route, so that characters are lined up with and facing their destination for the final part of the movement, giving them more of a sense of purpose in approaching the destination.

Using these priorities, the program can procedurally check each possible standard move, in decreasing order of desirability, and check for obstructions using RM's passability checker. In the example there are only 8 possibilities; this is typical for most cases in Discrepancy. Time spent doing this is negligible, and in most cases a standard move is sufficient to close on the destination, as in this example.



What if a more complex route is needed?



There is one very simple situation in which a standard move would fail--if the destination is directly in line with the starting point, but with an obstacle in the way. This would require the character to jog out of the direct line, and then jog back in, which is impossible with a single standard route. Also, rooms with complex geometry or many obstructions would cause a standard move to fail. In such cases, the program attempts to connect the start and destination points by stitching two standard routes together. The first route takes the character to a mid-point that I call a "node", and the second route connects the node to the destination.



Of course, finding the two best standard routes requires finding the node, a point on the map that is accessible from both the start and the destination. Here the program falls back on less efficient precedural-checking methods.

Finding the best node.



First, the program goes through every single tile on the map to create a list of which tiles ARE accessible from the starting point by a standard route.



Then it goes through this list of possible nodes and attempts to connect each of them to the destination via a standard move. Whichever nodes pass this test represent points that are accessable from both the start and destination, I.E. valid nodes to connect the start to the destination.



Of the various nodes that would connect the start to the destination, the one must be chosen which results in the most efficient overall path; i.e. the shortest path. In the example above, we can see that the circled node is the best choice, but how can we transmit this logic into the pathfinder?

Counting the number of steps is not the best method, since there are several routes with equivalent numbers of steps (given that a diagonal step, while appearing to cover more ground, is counted the same as a non-diagonal step) that would give the appearance of the character covering unnecessary distance. Instead, the Pythagorean theorem (Aaahhhhhh!!) is used to select the node that gives the appearance of the least overall distance travelled by the character, hence resulting in the most logical route. In the example above, the circled node results in the smallest straight-line distance from the starting position, to the node, to the destination.



The final route looks very fluid and natural in execution, and the fact that it is two seperate routes stitched together is not obvious.

But finding the node takes time ...

There is a noticeable pause whenever the program must stitch together two standard moves to form a route. Checking every single tile of the map to create the list of possible nodes, and then checking every one of those nodes against the destination, is a time-consuming process. The square-root function required by the Pythageorean theorum (Aaiaiieeee!!!) also takes considerable processing time.

The pause can last up to a second, which in game design is damningly long, but I've detemined that the pause is acceptable for the following reasons:

Most routes in the game are found using a single standard move, so the second one is not needed often.

Every map in Discrepancy is predictably small. As described above, every map is only 22 x 18 tiles, and the area of the map checked for nodes can be restricted even further to only the "usable" region not off the edge of the screen or covered by the menu, so I can be sure that the pause will never be any longer than previously observed.

There is also a measure in place to reduce the number of these pauses in-game. When the pathfinder must use a second standard route to connect two particular points in the map, the final route is saved to a database for future reference. If the same path is ever called upon again, the program simply reads the path from the database instead of calculating it all over again. Hence, the ungainly pause only happens the first time a complicated path is called for.

This database method only works because, as noted above, in this game characters always return to their initial position after performing an action. For example, a player will walk to an item to pick it up, and then walk back to their starting position, without exception. Hence, the starting point of the character, and the positions of other characters on the screen (which constitute obstacles) are predictable.

As an additional measure, once all the maps are made, I can run a program that loads every map and checks all the most typical routes that will be used in the game, pre-emptively saving many of them to the database, and then writes the database to a file. The file will ship with copies of the game, which can simply load the database and be instantly equipped with many of the routes that would otherwise have resulted in a pause during gameplay while they were constructed.

But what if even two standard moves is not enough?

What if the destination isn't accessible even with two standard moves? Well, one strategy for adding a THIRD standard move would be to search for a second node from the destination's side. To find the first node, remember, the pathfinder created a list of which tiles that were accessible via a standard move from the starting position. Now, the program could conceivably create a list of tiles that are accessible from the destination, and then check each one of them against each starting-side node; if a destination-side node can access a starting-side node via a standard route, then a route is created that completely connects the starting position to the destination.

Of course, the processing time required for such an extensive process is beyond the boundaries of acceptibility, especially considering the particular needs of this project, and the fact that the actual layout of different maps doesn't affect the difficulty of gameplay. If two objects aren't joinable by two standard routes, the game just screams and explodes, which will alert me to re-design the map to make the objects more accessible to each other.

End of the article.

Well gee, I hope you enjoyed my journal. Was it boring? Informative? Did you like the colourful diagrams? As I said above, I haven't provided any code because the pathfinder is not easily transplantable into other projects, but I will respond to demands. Thank you for reading it, if you did.

Posts

Pages: 1
Oh God my head nearly exploded when I scrolled through all this thinking it was 2k3. This is still impressive, of course. Good job!
There was a tutorial somewhere on impeenting A* Pathfinding in RM2k3, but I really would encourage you to find a way around it.
Gibmaker
I hate RPG Maker because of what it has done to me
9221
author=Pokemaniac
Oh God my head nearly exploded when I scrolled through all this thinking it was 2k3. This is still impressive, of course. Good job!


Oops. Yes, I suppose I should have said that it was an RMXP project. :P Thank you.
Pages: 1