Simplistic Pathfinding, How This Might Work?
by Clark Kromenaker · in Torque Game Engine · 12/07/2005 (6:33 pm) · 8 replies
I was looking at the pathfinding tutorials on the site and, while they looked useful, I wasn't interested in BOT creation and they all seemed a bit too complicated for what I needed. So, I had a thought.
I used 3D Gamestudio for awhile, which is fine, but I didn't care for some aspects of it. I read a tutorial while I was using it on a simple sort of pathfinding. Basically, two rays extend outward from the player, one in the front-right and one in the front-left. So...
------------ray1 (turn right)
----------/
PLAYER ->front
----------\
------------ray2 (turn left)
When a ray hits a piece of level geometry, the player turns away from it and continues forward. So, if there was a piece of wall between a destination and the player, he would walk towards the wall, but then a ray would hit it and he would turn until the wall was no longer in front of him. He would then move forward until the ray no longer collided (signifying an opening in the wall) and go into it.
It's extremely simplistic (I don't even know if you'd call it pathfinding), but its all I would really need for my game. I was wondering whether this can be done easily in Torque and how I might do it?
Thanks,
Clark
I used 3D Gamestudio for awhile, which is fine, but I didn't care for some aspects of it. I read a tutorial while I was using it on a simple sort of pathfinding. Basically, two rays extend outward from the player, one in the front-right and one in the front-left. So...
------------ray1 (turn right)
----------/
PLAYER ->front
----------\
------------ray2 (turn left)
When a ray hits a piece of level geometry, the player turns away from it and continues forward. So, if there was a piece of wall between a destination and the player, he would walk towards the wall, but then a ray would hit it and he would turn until the wall was no longer in front of him. He would then move forward until the ray no longer collided (signifying an opening in the wall) and go into it.
It's extremely simplistic (I don't even know if you'd call it pathfinding), but its all I would really need for my game. I was wondering whether this can be done easily in Torque and how I might do it?
Thanks,
Clark
#2
I think the method used in 3D Gamestudio was to place two invisible models in front of the player which checked for collision and moved the player accordingly. I don't know if I could do this with Torque, though.
12/07/2005 (7:02 pm)
Well, maybe "ray" wasn't the best word...maybe saying something which is a bit in front of the player and checks for collisions would be better. Also, I'm not really planning on making a shooting game...all deaths would be completely scripted and I would only use this for the Player which the user controls. I think the method used in 3D Gamestudio was to place two invisible models in front of the player which checked for collision and moved the player accordingly. I don't know if I could do this with Torque, though.
#3
The first secret to success in TGE is to forget everything about 3DGS and the way it does things.
Secondly, you are really trying to re-invent the wheel here.
What you aren't taking into consideration is the fact that the engine already has two very fine functions for collision detection.
Also you already have the "something infront of the player" it's called the collision box.
If you really want to use something like your talking about the easiest way might just be to expand the collision box in the direction you are facing.
I dunno anyways, sounds like a cool idea, I was assuming you were talking about the raycast functions though.
12/07/2005 (7:19 pm)
I originally came from 3DGS too.The first secret to success in TGE is to forget everything about 3DGS and the way it does things.
Secondly, you are really trying to re-invent the wheel here.
What you aren't taking into consideration is the fact that the engine already has two very fine functions for collision detection.
Also you already have the "something infront of the player" it's called the collision box.
If you really want to use something like your talking about the easiest way might just be to expand the collision box in the direction you are facing.
I dunno anyways, sounds like a cool idea, I was assuming you were talking about the raycast functions though.
#4
http://www.red3d.com/cwr/steer/gdc99/
http://www.red3d.com/cwr/papers/1999/gdc99steer.html
etc...
I saw those papers a few years ago and I found it interesting.
I think what you're talking about has been implemented before with some success. I also agree that Torque's collisions already do some of that. But maybe not to the degree you're talking about.
12/07/2005 (7:34 pm)
A lot has been written on steering:http://www.red3d.com/cwr/steer/gdc99/
http://www.red3d.com/cwr/papers/1999/gdc99steer.html
etc...
I saw those papers a few years ago and I found it interesting.
I think what you're talking about has been implemented before with some success. I also agree that Torque's collisions already do some of that. But maybe not to the degree you're talking about.
#5
It's simply a matter of making sure "good enough" is really good enough--if it is, then steering is a really good design!
12/07/2005 (9:11 pm)
As Nmuta mentions, what you are talking about is steering, not pathfinding...two fundamentally different topics, but I personally feel as well that well implemented steering algorithms can achieve much of the benefit of true pathfinding to a pretty high confidence level as the much more cpu-intensive pathfinding algorithms.It's simply a matter of making sure "good enough" is really good enough--if it is, then steering is a really good design!
#6
12/08/2005 (6:03 am)
Pathfinding can be made as CPU expensive as a mere fraction of the time it needs to do geometry intersection tests with proper code. Pre-computed waypoint maps are insanely fast, at the expensive of eating lots of memory as the number of waypoints increase, but that can be fixed if you splie your markers in sectors and have "portals" between them. 
#7
@Dreamer: About which functions do you talk?
@Manoel: Could you explain you better? Could you tell me how to use waypoints?
Thanks !!
01/24/2006 (12:43 am)
Ouff, i'd like to get some help about this too.@Dreamer: About which functions do you talk?
@Manoel: Could you explain you better? Could you tell me how to use waypoints?
Thanks !!
#8
The basics is: for each node, calculate the paths to all other nodes, then store only the first node index for each path in your node. Each node will the then contain a table with the "next node" for evey other node in the map.
Pseudocode:
So let's say you want to go from 0 to 8. You read node[0].nextNode[8], and it returns "4". You go to 4, and read node[4].nextNode[8], and it returns "8". You go to "8". Done you arrived!
Of course, the more nodes in your map, the more memory the pre-computed map will take. But there are ways around that.
My preferred approach is using layered pathfinding. I have a map (root), that contains sectors (nodes) and each sector contains more nodes (nodes again). There are two pathfinding layers: between sectors and between nodes. Some nodes are defined as "portal" nodes that can lead into other sectors, and this is used to build the neighborhood information for sectors.
This way, I can use many sectors with few nodes, keeping the memory usage under control. To move from a sector to another, I just need to find a path to the nearest portal.
01/24/2006 (4:17 am)
Check this article.The basics is: for each node, calculate the paths to all other nodes, then store only the first node index for each path in your node. Each node will the then contain a table with the "next node" for evey other node in the map.
Pseudocode:
The map: 0 1 2 3 4 5 6 7 8
So let's say you want to go from 0 to 8. You read node[0].nextNode[8], and it returns "4". You go to 4, and read node[4].nextNode[8], and it returns "8". You go to "8". Done you arrived!
Of course, the more nodes in your map, the more memory the pre-computed map will take. But there are ways around that.
My preferred approach is using layered pathfinding. I have a map (root), that contains sectors (nodes) and each sector contains more nodes (nodes again). There are two pathfinding layers: between sectors and between nodes. Some nodes are defined as "portal" nodes that can lead into other sectors, and this is used to build the neighborhood information for sectors.
This way, I can use many sectors with few nodes, keeping the memory usage under control. To move from a sector to another, I just need to find a path to the nearest portal.
Torque Owner Dreamer
Default Studio Name
So in tight spaces especially, pathfinding is best accomplished by laying out path markers and then checking to see if the player is in the field of vision at each marker. If the player is, then you break the path finding routine, head to the player, kill him and head back to the path marker.