Gw Temp

Menu

Tutorial - 'RPG AI basics Part (2/3)' by Gorkan

An item about RPGMaker 2000 posted on

Blurb

Part two of Gorkan's AI Basics tutorial series! Read up chaps!

Body

RPGMaker AI Basics : Pathfinding (2/3)

By Gorkan



Here I am again (finally) !

This is the second part of my tutorial on pathfinding (first part here : http://www.gamingw.net/tutorials/711 ).
I’m sorry I kept you waiting so long for this tut, which should have been finished several months ago, but I lost most of what I had already written around July due to some (fortunately otherwise minor) problems, and then didn’t have enough time nor motivation to rewrite it completely.
I gave up for almost three months, but a few days ago I finally decided (thanks to the great feedback for the first part which gave me some motivation back) to use what was left from what I had previously written in order to make a tutorial explaining how to create a more or less dumbed down, but complete, version of my pathfinding system. Therefore, what will follow, albeit intended for experienced RM2K users, will be simpler than what I had originally planned, and I might eventually write the third part of this tut, explaining how to do the real thing, someday if I ever have the motivation.

(here are the diagrams from part 1, which I'll refer to again )


Warning : This is really for experienced users. There are things I will only give general directions about, rather than explaining them step by step (I think this tutorial is long enough already lol), and I suggest that you read the whole text, and try to understand it, before applying what it explains : don’t forget that tutorials aren’t recipes but guides to your own thinking ;-)
This being said, have a good read !


II.2 Probe and checkpoints

Since explaining a checkpoint-only method would be much too long without being of any use for the rail-checkpoint method, I’ll only expose the general principles of checkpoints and the probe here and then detail the realization of the final system in chapter III.

What I call « checkpoints » (this was the first name that came to my mind because, when used with the rail system, they act a bit like the checkpoints in racing games) are invisible static events without a single event command, that are placed at strategic locations such as crossways or every place where the path curves, in fact everywhere the NPC must chose a direction or there may be a « diagram #5 -like » situation.
They have multiple uses : they can transform « #5 » situations in « #6 » ones, which can be solved much more easily as I’ll explain later (here : if the NPC [red dot] wants to go to the red cross, he is in a « #5 » situation, but if he walks to the nearest checkpoint [blue square] first, he’ll be in a « #6 ») ; they also enable the NPC to elaborate more complex moves such as going from the red cross to the upper right checkpoint to the lower checkpoint to the green cross, and to choose in which direction to go at junctions. There are mainly two kind of interactions with the checkpoints : walking to the checkpoint or from it to a nearby target, and picking a path between checkpoints.

The former (walking to/from the checkpoint) is the one that will be developped here, with an explanation of how to do a very important part of the complete system, that you can also use as a complement to the rail-only method : the probe, or « #6 solver ». It’s a bit more complex than what I explained in the first part of this tutorial and I won't explain it with as much detail, since I assume figuring out some basic code won't be a problem for you if you can understand the advanced parts ;-)
The purpose of the probe is to determine if there is or not a path comprised between the X and Y coordinates of the NPC and his target, even in situations like this one (although there should never be really complex ones if you plan your pathgrid well), before he actually moves. In order to do that, you’ll need fork conditions, cycles, perhaps some labels and goto’s, and a great deal of switches and variables (although I tried to be economical) - you are warned.

Now, a step-by-step explanation : store the NPC’s XY coordinates in two new variables, probeX and probe Y, then set four other variables to [probeX]+1, [probeX]-1, [probeY]+1 and [probeY]-1. It’s very important to use the values of the former two variables in the « brackets part » of the latter four ones, and not the actual coordinates, since we’ll need a probe that searches for a path without the NPC having to move himself (which is why I used « probe » rather than « NPC » in their names).

The next step is to determine the pattern of the probing. If you prefer to keep the code as simple as possible, you may apply the same pattern over and over and just skip this paragraph, but if you want a system able to find instantaneously the good path in the simplest cases, just do the following : store the target XY coordinates in variables, and then substract the NPC XY from them. That way you can know in which directions to probe (trigger corresponding switches or set variables to specific values, you’ll need this information later), now multiply these values by themselves and compare them in a fork condition in order to determine whether the X distance to cover is bigger or smaller than the Y distance, and trigger a switch in accordance to your results (don’t forget the X = Y case) ; by combining both these informations you can determine an order of priority between the directions in which to probe.

In the following explanation, I’ll suppose that the NPC is in the upper left corner of a rectangular zone and his target in the lower right corner (the simplest case since target XY > NPC XY), right being the prioritary direction (bigger X distance to cross). Just create a few fork conditions in order to cover every possible case ; I’ll add comments between slashes « / » to help you extend this system to the other cases.

Start a cycle, and copy the previous part where you defined the four variables probe X+1 to Y-1, since you’ll need these ones to be updated after each « turn » (so it wasn’t really necessary to define them before, but it can be useful if you ever want to do some changes in the system).

The first thing to do, even if it doesn’t seem really logical, is to check whether the value of the variable probeY-1 is comprised between NPCY and targetY (since we’re making a cycle, we want something that will work at any point of the probing, thus this seemingly useless verification)
/Always check the opposite of the secondary direction (here, up, the opposite of down) before any other, you’ll understand why later./
Then, « SetTerrainIDize » the [probeX ;probeY-1] tile and check whether it is an obstacle. If it is in the Y fork and isn’t an obstacle, just substract one from probeY (which is like having the probe virtually step up once) and restart the cycle ;
/Then the primary direction : /
Else, check the [probeX+1 ;probeY] « right » tile (both by verifying that its X is comprised between NPCX and targetX, and with the SetTerrainID ; I don’t think it is useful to detail this process again so I won’t do anymore), and if there’s no blockade of any kind, add one to probeX and restart the cycle ;
/And finally the secondary direction itself : /
Else, check the [probeX ; probeY+1] « down » tile, and, if necessary, add one to probeY and restart the cycle.
A last little addition will be necessary for this system to work : after each step in a direction, activate a switch corresponding to this direction (and deactivate all other such direction switches) ; before even checking the « up » tile, verify with a fork condition that the activated switch isn’t « down », and so on, so that the probe doesn’t go back in the wrong direction - and naturally, stop the process when the probe reaches the target (by the way, sorry if you don’t like my way of mentioning now things that should have been done before, but it shouldn’t be too much of a problem to do some cut/paste in order to add more fork conditions, and if I directly described the final system without these intermediary steps, I think it would be much harder for you to understand the logic of its construction, since there may eventually be quite a lot of subparts and secondary processes in this system)

Finally, if probeY = targetY but the probe cannot move to the tile to the right, or if probeX = targetX and the probe cannot step down, activate a « probing failed » switch that will end the whole process.

Now you have a very rudimentary probe, that *will* solve #6-like situations (that is, determine whether it is possible to reach the target or not before the NPC tries), but not the more complex ones, and that won’t always chose the shortest path. In order to do such things, you’ll need to keep track of every movement of the probe - this is where data space problems begin to appear : it is unconceivable to use a variable or even a switch for each and every tile of the probed zone, even if you use the same variables for every new probing, cause if you want to grant to your NPCs the ability to probe on a large, e.g. 20x15, zone, you’ll need 300 variables per NPC on the same map ! If you can really afford such a loss of variables or switches (that can be reduced to less than 100 variables per NPC if you manage your checkpoints well, though), please do, it will greatly simplify the coding, but since this solution isn’t one for most of you, I’ll let the happy few find by themselves how to do it (a little advice if you don’t know how to start it : use switches for each tile which you’ll set to 0/OFF if the corresponding tile is an obstacle or if the probe « stepped » on it twice before reaching the target, once in one direction and another time when following its own track backwards because of a dead end, and set the switches to 1/ON for any other tile that the probe passed on its way to the target - then, before each step of the NPC, check for the next ON-switch, just like the rail ; reading the following and part III may help you to find a way to automatically determine the switch/tile attributions with cycles and such).

If you don’t want to use such a costly method, there’s another way to keep track of the probed path, but it’s really not as simple as the former : instead of generating a grid with the different positions of the probe, we’re going to gradually divide its path in horizontal or vertical segments during its progression.

You may use two variables per segment (one for the direction, and the other for the number of steps) but I’m going to explain how to store multiple segments in only one variable (now I may be overcomplicating the problem, really, but that way you can store 12 segments in only 4 variables instead of 12 ; if you prefer to use two variables per segment and risk less bugs, don’t bother doing what follows, but try to read it anyway : if you’re able to understand the more complex method, you shouldn’t have any problem in adapting it to simpler cases).
Variables in RM2K can store 6-digits numbers, therefore they can be used as six one-digit variables ; you will need two for each segment : one for the direction, and the other for the length. Any segment longer than 9 steps will be cut in two shorter ones.
Also, since we’ll need to easily retrieve the characteristics of the last segment with a modulo, we’ll start from the left in our variable and alternate direction and length

6-digits variable : [direction of first segment] [length of first segment] [direction of second segment] [length of second segment] [direction of third segment] [length of third segment]

Thus, if « 4 » corresponds to « up » and the first segment is three steps up, the variable (let’s call it «Stored Segments123 ») will store « 430000 ».
If « 2 » is left, a three steps up, two steps left, nine steps up series will be « 432249 » ; and a twelve up six left will be « 494326 » (nine up, three up, six left)

Now, in order to write these values in the right order, you’ll need to do the following :
Take a new variable, and name it « Segment# » or something like that. Now, before each step of the NPC, check if the « direction switch » (see a few paragraphs above) corresponding to the direction of the step is activated (you can also use the value of the direction variable, as explained below) and the segment is less than nine steps long, else add one to Segment#. Then, when you want to store the characteristics of a segment, set a temporary variable (by which I mean a variable used for calculus only, and needed a limited amount of time before being used for another operation) to Segment# modulo 3. Using a fork condition, determine if the result is 1, 2 or 0 : if it’s 1, then the segment is the first, or the fourth, or the seventh .. and you must multiply its direction number by 100,000 and its length by 10,000 before adding them to the corresponding variable (StoredSegments123, or 456, and so on ; I explain how to determine which one in the next paragraph) ; if it’s 2, second or fifth segment, multiply the direction number by 1,000 and the length by 100 ; and if it’s 0, third or sixth segment, by 10 and 1.
Thus, if you later want to know if the direction of the second segment was left (« 2 »), just set a temp variable to StoredSegments123 modulo 10,000 and check whether the result is comprised between 2,000 and 2,999.

As for the more-than-one-storage-variable part : set a temp variable to Segment# minus 1, then modulo 3 on the result. Now set another temp to Segment# minus the result of the previous one, minus 1, then divide by 3 and add the result to the variable # of StoredSegments123 (the first of these variables) to get the number of the variable used to store that segment.
A bit tricky, I know, but look :
If StoredSegments123 is variable #3000, StoredSegments456 is variable #3001, and so on, then

Segment# ; - 1 ; mod 3 ; Segment# - result ; - 1 ; / 3 ; 3000+ result ; variable
1 0 0 1 0 0 3000 SSegm123
2 1 1 1 0 0 3000 SSegm123
3 2 2 1 0 0 3000 SSegm123
4 3 0 4 3 1 3001 SSegm456
5 4 1 4 3 1 3001 SSegm456
6 5 2 4 3 1 3001 SSegm456

Ta-Daa ! (if the graph above doesn’t show correctly, here it is in image format : )
A little note : I don't remember whether I already mentionned this before or not, when you want to set the value of a variable which number - or address, if you prefer - is itself variable (like above), go in the "Change Variable" function, tick the third option (with Variable Number on the right) in the "Create Variable" box, and select the variable which value is the number/address of the variable you want to change (do you like variables ? I like variables).

This way, you'll also be able to extract data from the variables anytime, knowing only the Segment# (you'll have to code the whole thing once for the writing and the reading processes, and then you can copy/past it everywhere you need to read or change these values, for instance when checking the direction of a segment, or when adding one to its length after each step - you can also set it as a common event, which makes the whole deal quite simpler but can lead to confusions - but anyway don't forget to replace the corresponding parts of the old code with the new ones)

Note : If you really aren’t able to figure how to do some of these things, don’t hesitate to ask questions, I may even write an annex to this tutorial, but only experienced users should be trying to follow this tut (I suppose the newbies quit reading this long ago anyway *lol*)

Now, if the probe doesn't find the right path at first, it'll eventually end up in a dead-end. Ideally, it should be able to follow its own track backwards and chose another path. But as I said before, I won’t explain how to do this more complex version here, since it isn’t really needed (you can do almost as much, and quicker, by using the simple probe and adding a few more checkpoints at the crossings instead) and would take quite long.

When the probe finally reaches the target (that is, when the probe X and Y coordinates equal those of the target), stop the whole process and then have the NPC follow its path by reading the StoredSegments variables : set a temporary variable to the number of steps of the first segment, and then start a cycle that substracts one from that variable at each step (use a fork condition in order to determine the direction of the step) until it reaches 0, then go on with the next segment (do the same with the Segment# variable as with the number of steps) till the NPC finally arrives at the target.


III. Final System

Finally, we get to the point of the whole thing ! (anyone still alive around here ?)
You are warned : no more step-by-step beyond this point, all the techniques you need have already been explained, now I only explain their application.

Okay, first, here’s a brief summary of what the system is supposed to do exactly :
Let’s suppose a NPC guard is attacked by the hero, and he screams before dying. We want every other guard to come looking for the origin of the noise, wherever he may be to begin with, and to use the exact same code for other maps with guards. We can do this by using the rail technique, but only if there aren’t multiple paths.
If there are, we need the NPCs to get to the crossing, then decide which way to go (and going in the general direction of the target isn’t always very efficient). This can be done by putting « milestones » at every crossing and then having the NPCs going from one chekcpoint (milestone) to another and so on until they finally reach the point where there is no more obstacle between them and their target.

In order to do this, we’ll need to quickly determine a path that will lead to said target, before the NPCs even begin moving (else they’ll wander seemingly aimlessly for hours until they finally find it by pure luck, which isn’t very appropriate for emergency situations), which implies knowing which checkpoints are intermediaries between the one that is nearest to the NPC’s original location, and one that is near the target. As soon as the hero arrives on the map, every checkpoint must therefore « know » which other ones are near it and how to get to them .

The SetEventID function will be very useful in order to identify the checkpoints, thus making it possible to create such a pathgrid. Hence, all checkpoints should have a « special » ID (not completely random) : I suggest to place them either before any other event, and the coordinating event (the one that will determine all the paths) right after, so that it « knows » that any event with an ID smaller than its own is a checkpoint, or alternatively to put them when every other event has already been placed, with the coordinating event just before, for the same reasons. You can also manually specify the IDs of the first and the last checkpoint in specific variables for each map if you prefer.

I admit I lied when I said that the checkpoint events do not contain a single line of code ; they actually contain two (in autostart or parallel process mode, it only needs to be done once when the hero arrives on the map) : two Set Variable functions, that will set two CheckpointX and CheckpointY variables to the corresponding coordinates. In order to find these variables easily later, their address should follow a model : for instance, let’s say you want to use your first 2000 variables for other systems and so on. Have every checkpoint event check its own ID, set it into a temporary variable, and then multiply said variable’s value by ten. Add 2000 to it, and 1 for the X variable, or 2 for the Y variable : thus, checkpoint #2’s X coordinate will be stored in 2000+2*10+1=2021 (if its EventID is 002), and checkpoint #19’s Y coordinate in 2192.
Aside from that, the checkpoints will only be used passively, so you can even use them for totally unrelated things once you have their coordinates (although they have to stay at the same place).

The coordinating event is one of the keystones of this system. As soon as the map is loaded, it will create an index of the checkpoints and their relations. In fact, it uses something that works more or less like the probe : starting from the coordinates of the first checkpoint, it either probes or follows the rail (if you created rails connecting all the checkpoints – but the coordinating event does not move itself, use a probe-like system) in the four directions, until it finds another checkpoint (setEventID at the coordinates of the probe after each step, if the ID is smaller than that of the coordinating event, it is a checkpoint), and then it stores the ID of the checkpoint found by going up in variable # (2000 + (1*10) + 3), or the checkpoint to the left in variable #(2000 + (1*10) + 4) and so on.
When it’s done with the first checkpoint, go through it again with the next one (ID 002) until you finally reach the coordinating event’s ID, then stop. This may cause some loading time, especially if the map is big and on older machines, and it can be greatly optimized, but I’ll explain how in the third part of this tutorial, if I ever write it.

When your index is created, you’re almost done. Now, when a NPC wants to go somewhere special (it shouldn’t be used too often, else your game may become quite laggy), first determine with a probe which checkpoint he is near (compare the coordinates of the NPC and the checkpoints, then probe in the direction of all the nearest ones in order to find one that can directly be walked to) and which one is nearest to the target.
Then his path is established by a « meta-probe », that works exactly like the common probe, only with EventIDs rather than coordinates : it compares the X and Y coordinates of the origin and target checkpoint, then, instead of going through the cycle again with Y-1 for instance, does so with the checkpoint whose ID was stored in [variable # 2000 + (firstCheckpointID *10) +3 ], and instead of checking the next tile for an obstacle, checks [var # 2000 + (currentCheckpointID *10) +3 ] (this is what I’ll call a « directional ID », since it’s the ID of the checkpoint that can be reached by going in a precise direction ) to see whether its value is 0 ; all the while, it memorizes the IDs of the events instead of segments and number of steps.

When the meta-probe finally reaches the last checkpoint, the NPC can move : he probes then walks to the first checkpoint, and then goes from checkpoint to checkpoint by comparing the « directional IDs » with the stored ones, until he arrives at the last one, where he probes / walks to the the target.

Magical, isn’t it ?


Okay, there’s a hundred ways the code can be improved so that the system is less ressource consuming or more efficient (for instance, by dividing the map in sectors that act like checkpoint-areas and possess a list of all the events they contain, and so on) and I’m sure if you can make the basic version, you can also find ways to optimize it by yourself, but anyway, if I ever write about them, it will be in the third part of this tutorial ; I think the second’s long and complex enough for now (and I rewrote most of what was missing in a single evening, tonight that is, which is why I am beginning to tire a bit … lol)



As I said before, don’t hesitate to ask questions if you have a problem (but don’t forget that small errors are easy to overlook in a system that big and complex) or if you consider that my explanations really are too thin or unclear (I can easily understand that, especially in chapter III, which I rushed a bit)

If you read the whole thing : Congratulations !

If you read the whole thing in only one sitting : You really outta see some psychanalyst … I recommend mine, he’s always very nice with me.

If you read the whole thing in one sitting, and understood what I wrote and how to make it without even having to think twice about it and then actually MADE it : Come, let’s enjoy the little fluffy rabbits, especially the pink ones who dance the charleston !

If you just read the first few lines and then jumped directly to the end : Wabbajack !


Thank you very much anyway ! (yes, even if you just read the first few lines and then jumped directly to the end lol)

Now I may consider getting some sleep, yay …




- Gorkan