Game Development Community

dev|Pro Game Development Curriculum

RTS Kit Basic Pathfinding

by John Eckhardt · 11/07/2006 (12:21 pm) · 9 comments

Download Code File

Here it is! I got tired of not seeing a decent RTS pathfinding resource around here (that and I needed something to work for my project), so this is what I came up with! It does not take any engine modifying, just a script file or two.

How It Works:
First off, I'll explain how it works, feel free to follow along in my well-commented code. Now, there are three different scenarios with a rectangle object pathfinding. (View the picture)

1. There is no object between your unit and its destination. Simply go to the destination!

2. There is one corner between your unit and its destination.
a. Find the closest side to the direct line to your destination. (side x1)
b. Find the closest corner on that side to the direct line. (x1, y1 or corner A)
c. Move to that corner. (plus an offset value so you aren't in the object)
d. Calculate the new path to your goal which is Situation 1 now.

3. There are two corners between your unit and its destination.
a. First, follow steps in Situation 2
b. Find the closest side to the direct line. (side y1)
c. Move to the FARTHEST* corner on that line from your direct line (x2, y1 or corner D)
d. Now we are in Situation 1 with no object obstructing our path to our destination!

Theoretically, this should work with all objects with bounding box sizes of 3, 4, 5, 6, ... sides, but I have no clue how to make a bounding box on an object different than a square

*Why go to the farthest corner?
Now if we calculate the next waypoint the same way as the first, this is what happens. We have just arrived at a corner. The closest corner on the new side our direct line passes through will be this same corner! Thus, if we go to the closest corner on the line, we will be going back and forth between the offsets from this corner for all eternity! Rather, if we pick the farthest corner, we are back in the game.


Now that's how it works, go have fun with it!


Install:
1. The fun code is inside the download file. Copy it into your server\scripts\avatars directory. Most of you shouldn't have anything useful in the pathManager.cs file anyways.

2. Add the marker which keeps track of how many waypoints we have done (used for when we choose the closest or farthest corner) into server\scripts\avatars\player.cs. 3 changes noted in the Player::onReachDestination function.

if(%this.curGoal $= "")
   {
      echo(%this @ " - Arrived!");
      %this.didWP = 0;  //added
      return;
   }
   
   
   %nextWP = PathManager::getNextWaypoint(%this.getPosition(), %this.curGoal, %this.didWP);  //added third argument
   %this.didWP++;  //added

Then, it should work!

What this will do:
1. It will let your unit find its way around square-bounded objects, taking the shortest path.
2. It works with multiple units, each finding its own path.
3. It will work with multiple objects in the unit's path.

What this will not do:
1. It will not find a way around other units. This was built to walk around static (non-moving) shapes. For example, if you tell it to walk around a 'moving building' it would find out where it's supposed to go, then move to the corner of where the building WAS when it figured out where it should go to avoid the building. So this could be a needless course off into empty space, or through the building! And then it would defeat the purpose of walking Around the building.
2. This only walks around objects bounded with a square, so if you have a more complex object, I'm not sure how it would react. Maybe it wouldn't be able to find a corner? Or maybe it would work. Either way, I am not saying it does support hexagonal or other -gon object traversing.
3. If you have massive amounts of units (say in the 100+ range) all going on the same path, this won't be the fastest way to pathfind. It would be better if they have leader units so you can pathfind for them, and the others can follow.

Credits:
Robert Stewart got me started on this, I tried to use his pathfinding with countless hours of non-success, so I tried on a whim putting some of his code in a different place, and I got it to work! So thanks for the concept!

Tested under TGE1.4 with RTS Kit (whatever build is out now)

#1
11/07/2006 (2:47 pm)
does this also work if you have a complex model but a square collision box?
#2
11/07/2006 (2:49 pm)
Yes, it uses the %obj.getWorldBox to find the coords for the bounding box. So it shouldn't matter how complex the object is, as long as it has a 3+ sided bounding box.
#3
03/26/2007 (11:58 am)
Hello,

First off, thanks for the help!

I have a question tho, I have simply dropped the *.cs file into the directory, however the units still walk though objects (buildings).

Whats up?
#4
03/26/2007 (2:12 pm)
It doesn't check for buildings or the regular player character (the units) because it would need to check each game cycle in case they have moved, and you'd have to plot a different course. So it's only for static objects.
#5
03/30/2007 (10:06 pm)
@John

did it work for you?

Because I am finding that it doesnt work...
#6
07/11/2007 (3:11 pm)
I dont know why you put A* pathfinding on the keywords
#7
07/11/2007 (4:17 pm)
Novack - perhaps because people interested in A* might be interested in this as well ?
that's exactly what keywords are good for.
#8
07/11/2007 (6:50 pm)
Yeah, while this isn't an A* pathfinding, it would be useful for some people (like me) to find other easier ways to do some pathfinding. And I just might search for A*.
#9
07/30/2007 (7:15 am)
Ok, sounds reasonable.

(Nevertheless, I dont agreed about "what the keywords are for", I think the keywords are to put words related to what a post is about, and not words supposedly related to the topic. Just imagine for example, what happend if we have 5000 post about pathfinding, but I just want A*... This is not the case, beacuse there arent such number of post about pathfinding, but you see my point)