Pathfinding in a non-waypoint space.

Hi all. I’m trying to make a pathfinder that doesn’t need waypoints, or something similar.

I’m thinking about make a lot of traces to find what objects are obstacles and where they ends, to reach there and look for the next path. Something like:

http://img651.imageshack.us/img651/7314/pathfinding.png

The purple traces are the first step, determine when the object finish. The grey traces are the second and third steps.

Green points are “waypoints” found via tracing around to find the end of the obstacle.

I thought that about traces but… Infinite traces I need.
I thought also to get the physics box (or whatever it is named) of the entity, works but map because whole map (worldspawn) is a single entity…

And I’m out of ideas. So, any help will be useful.

Thanks for read.

Something that will definitely prove useful: http://wiki.garrysmod.com/?title=Util.TraceHull
(A TraceHull is like a TraceLine, except instead of tracing along a line, you’re tracing along a box)

Pretty shit diagram and it can probably be done more efficiently than this but:

http://img59.imageshack.us/img59/1214/tracehulls.png

There’s an initial trace straight to the destination, which hits an obstacle.

From there, traces to the sides. One hits an obstacle, but the other doesn’t

So we do a few traces along the valid trace. Again, the first failing, but a later one being mostly clear, so we follow this one until it gets to a line perpendicular to a line traced through the start point and destination (well, roughly.)

We then try another trace to the destination and succeed.

In practice, of course, you would probably only want to calculate a couple traces ahead, in case something blocks the path, and if the npc stops moving for any reason you would recalculate it entirely.

Ah, good. Now I know I need TraceHull instead TraceLine.

But I still have a problem. Where to aim TraceHull? I mean, I can use TraceHull infinite times to get the real shortest path, but it is so expensive to processor.
Or maybe I’m idiot… I prefer to think I’m not :P.

Updated my above post with an explanation, the diagram should make more sense and help you out more now.

Calling player p, and finish point m:
The first path is from p to m until hits an obstacle o. This point is going to be l.
The second path is from l to… To where? I think it must be parallel to the obstacle.
But to make a vector I need start point(l), direction (parallel to o) and FINISH point (unkown).
And the red line… If there is another obstacle I won’t need to cross it (I think)?

Anyway, thank you so much for try to help me.

Let P stand for the player’s original position,
Let M stand for the destination,
Let O stand for any obstacle.

Run a tracehull from P to M.
If O is encountered, let L be the point at which the trace hits O.
Now subtract 16 units (since the player is 32 units across, we need some room) from L in the direction of the player, lets call this T:


T = L+((P-L:Normalize())*16)

Now, make some perpendicular traces:



local vecangle = L-P:Normalize()
local rotangle = Angle(0, 90, 0)
vecangle:Rotate(rotangle)

tracedata.start = T
tracedata.endpos = T + vecangle*10240
tracedata.mins = ply:OBBMins()
tracedata.maxs = ply:OBBMaxs()

local trace = util.TraceHull(tracedata)


(Repeate the above code but where it says “Angle(0, 90, 0)” replace that with “Angle(0, -90, 0)” to get the other trace in the other direction)

Now find the distance between the startpos and endpos of each trace, and find the smaller one. If both are less than, say, 32, use some of the above code and have it run back and do traces from farther back on the line. Assuming one is less than, however, begin a series of traces along our virtual line.



--assuming the 90 degree rotation was successful and not the -90
local oldangle = L-P:Normalize()
local vecangle = oldangle
local rotangle = Angle(0, 90, 0)
local vecangle:Rotate(rotangle)

tracedata.start = T + vecangle*32
tracedata.endpos = T + vecangle*32 + oldangle*10240
tracedata.mins = ply:OBBMins()
tracedata.maxs = ply:OBBMaxs()

local trace = util.TraceHull(tracedata)


You would put that in some kind of loop and have the 32 increase by 32 each time until you found a fairly clear path.

This is probably a load of really messy code and there’s got to be an extremely more efficient way of doing all this, but it’s a start.

But that can fail if the path width is less than 64. For instance, there is an object that ocups 0-1, and another object that ocups 63-64 (two superthin objects):

This shit represents über thin things:


-        -

This the tracehull:



_____
|   |
-        -


It collides with first thing.
Then add 32, and try again:



     _____
     |   |
-        -


Now it collides with second thing. Where a human can find a path, the code can’t:



  _____
  |   |
-        -


Any idea about that?

By the way I’m still thinking that a loop of infinite traces of Hull until find the path is really really expensive…

Yeah, lots of traces of any kind, especially a lot in one frame, get expensive. I know somebody else made a pathfinding script somewhere, perhaps take a look at that and see what you can learn?

Yeah, there are scripts about pathfinder. But based on waypoints.
My main problem is that, get waypoints from obstacles…

http://www.facepunch.com/showthread.php?t=254059
I’d take a look at the A* Pathfinding Module, it’s a very efficient way to pathfind.

Uses a waypoint system.

[editline]08:34PM[/editline]

(Not the kind of waypoints in the OP)

Well, any real good pathfinding system should use waypoints, really and truly.

Above post is very true. Especially in a 3D environment.

Unfortunately, he apparently does need a system without waypoints (hence the title of the thread, hehe…)

Anyway, Gbps, I know you’re a fairly excellent coder, perhaps you could adjust some of my above posted code? I think that’s about as efficient as it’ll get in terms of number of traces, but not very effective. And some of my math and stuff may be faulty.

I would help, but my expertise is not in the field of AI.

Hmm… about the problem with ultra-thin things. Perhaps there’s a possibility that tracehulls and tracelines could be combined? Perhaps a system could be formed that uses tracelines as kind of a “virtual sight” to get a general direction and idea of clearance and then tracehulls to confirm a path?

Also, it would be good to know how variable the environment is. For example, are there going to be hordes of zombies moving that could cause collision issues and require a lot of path recalculation, and therefor simpler calculations. Or is it going to be in a relatively calm environment where most of the objects stay relatively still and the path doesn’t have to be recalculated as often?

Either way it would be a he’ll of a lot easier to create a grid of waypoints near the desired area and go from there.

A video of my autonoder (I will fix up and release this if you insist).
Since this video, I’ve modified it to account for hull sizes.

My A* pathfinding module: http://wiki.garrysmod.com/?title=A-Star_Pathfinding_Module

A demonstration of the module in LOVE (A 2D game engine that uses Lua):
[media]http://www.youtube.com/watch?v=xSKu7QNayuA

(my heuristic was fucked up when I made this video… the paths are munted)

Omg. It seems very good. Sure I’m going to insist :P.
And well, you all say I should use a grid of waypoints (or something), but eh, we are playing garrysmod.
There is not a game more “dynamic” than garrysmod. In counter you can do waypoints because the map won’t change, but in garrysmod you could do a whole map with entities, block paths with props, etc…

You can block paths with props in CS:S, the point of having waypoints is to decide if an area can ever be walked on or not.