 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Precalculated Pathfinding Revisited |
|
 |
superpig GDNet Technical Lead Member since: 5/26/2001 From: Oxford, United Kingdom |
|||
 Posted - 5/12/2003 11:25:49 AM |
||||
No feedback yet?  A chap by the name of Stephan Hodes has mailed me, with the suggestion that the whole precalculated pathfinding problem may have already been solved a while back - with TCP/IP. Packets need to be routed from place to place without knowledge of the whole internet, and it copes with links going up and down all the time, so it might be worth a look. As far as we know between us, it's not been applied to AI pathfinding, but it seems a cool idea. Superpig - saving pigs from untimely fates, and when he's not doing that, runs The Binary Refinery. |
||||
|
||||
 |
SarsDP Member since: 2/27/2003 |
|||
|
Posted - 5/12/2003 12:16:09 PM |
||||
| That was a great article, I'm going to try to use that in my next project. |
||||
|
||||
|
jofferman Member since: 8/5/2002 From: The Netherlands |
|||
|
Posted - 5/13/2003 3:19:12 AM |
||||
| I tried to mail this yesterday, but it bounced (check your e-mailadress?), so I'll just post it here: Hey Richard, I've just read your "Precalculated Pathfinding Revisited" article on Gamedev... nice technique, very elegant. Though I was wondering what your take is on the problem of scalability, as it seems to me that your solution isn't very scalable (yet). For example, we're currently working with levels that have at least 256x256 tiles. Assuming the worst-case scenario where every tile is classified as "passable terrain", we'd need at least a 65536x65536 look-up table of shorts, that's 8 GB! That's not gonna fit on our CD... :-(. By comparison, a simple waypoint network (where each waypoint only stores connections to the adjacent nodes; so for a simple heightfield terrain there's a maximum of 8 adjacent nodes) requires a minimum of 65536x8 shorts (= 512 kb) to cover the same terrain. Obviously at the cost of needing to recalculate a complete path every time. A hybrid solution might work though, where there's a 64x64 precalculated pathfinding table that is used to quickly solve the "where to go next" problem on a large scale - i.e. how to get from base in sector (2, 2) to the enemies in sector (6, 4). Once a unit has decided on it's overall direction, a small waypoint network is used to further solve the pathfinding problem. (In our 3D engine we even have one more step, where the collision detection system decides how a unit moves from one waypoint to another) Kind regards, Jim Offerman Crevace Games www.crevace.com |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 5/13/2003 4:34:56 AM |
||||
| There is also the problem of pathing around dynamic objects. Entities themselves might block connections between nodes, if only one entity is allowed to occupy a node at a time. There is no method given for finding a path around this occupied node, except for recalculating all of the pathing data. But recalcuating all the data every time something moves into a new node would require more calculation than simply finding a path on a network in the first place. |
||||
|
||||
|
rrc2soft Member since: 5/8/2001 From: Spain |
|||
 Posted - 5/13/2003 4:49:30 AM |
||||
| Thx superpig for the article. That was what i needed BTW, Your algorithm can also be used in maps with different "zones": imagine a map with a town and the interior of the houses, separated by the void... using teleporting info you can resolve paths between those zones (teleporting eggs are nodes in the pathfinding algo) jofferman: It's not necessary to save every tile in your pathfinding table. Only use as waypoints the corners of a map. Why? 'Cause the corners see everything in a map. Your path is corner-corner-corner, and use a bresenham between corners. Check http://www.geocities.com/rrc2soft/eng/doc/AStarEn.html. It's an old, crappy and bug-filled algo, but i'm sure you'll get the point about using corners with Richard's algorithm (don't forget to check "Set Corners") ...and BTW, sorry for my engrish  |
||||
|
||||
|
superpig GDNet Technical Lead Member since: 5/26/2001 From: Oxford, United Kingdom |
|||
|
Posted - 5/13/2003 7:10:21 AM |
||||
| jofferman: rrc2soft is exactly right; why put a node on every tile? You only need them at significant points, like corners or junctions. If, as you said, every tile in your terrain is passable, then you'd only need one node to cover it, in the middle of the map - from there, a 'terminator' algorithm could simply head for the target in a straight line. When it comes to scalability, the 'subnets' approach was meant to help solve that. Yes, it depends on areas of the map dividing up OK, but that can be done more often that it may seem at first glance. Got a Delta-Force style hillscape? Each hill could have it's own subnet, with the points on the tops of the hills and the bottoms of the valleys as the Level 0 nodes. (My email address is fine.. hmm. You're not the first person to have problems, I'll talk to my webhost. If you could forward the bounce message to my other address, rfine@lycos.com, it might help )AP, a lot of it depends on the type of map. I always planned the 'ripple recalculation' approach as being a solution to dynamic objects; and it works just fine, *provided that* for any given route, there are alternate routes not too far away. If I had a house with a front door and a back door, and the front door were closed, the nodes outside the house would have to be redirected to the back door. That could be a problem if a whole load of nodes aimed straight for the house; if, however, I made walls around my house such that nodes had to direct to the front gate, then only nodes within the gate would be affected. It's that use of 'gates' that would keep processing time low; you perhaps can't use them in every situation, but no technique fits all cases. Also, when it comes to an entity sat on a node or path, a 'near-enough' zone can be established around the node or path so that the AI doesn't need to stand dead-center (which would look strange anyway). Detecting and dealing with temporary blockages, though, like other AI agents.. hmm. Sounds like a problem worth addressing. My first thought would be to split the path into three sections - the first 'clear' section, then the blocked section, then the final 'clear' section; then it becomes a question of navigating from the node between 1st and 2nd sections to the node between 2nd and 3rd sections. Superpig - saving pigs from untimely fates, and when he's not doing that, runs The Binary Refinery. |
||||
|
||||
|
jofferman Member since: 8/5/2002 From: The Netherlands |
|||
|
Posted - 5/14/2003 4:40:24 AM |
||||
| Ah yes, I think we're just using slightly different terminology. In our engine, a waypoint network is something that's generated off-line from the 3D mesh of a terrain and then used as input for the pathfinding system. We're also not really looking for the shortest path from A to B, but rather the fastest path - that is, if A and B are seperated by a huge mountain, our units should take the fast route around the mountain, rather than the short one that goes over it. So, even if the entire terrain is deemed passible, we need more than one waypoint to cover it in sufficient detail for the pathfinding system to make intelligent decisions. Of course, we could use the precalculated pathfinding as presented in the article to navigate that waypoint network, but it would be hard to incorporate some of the things we're planning to do - like allowing small units to pass through a narrow canyon, while forcing larger units to move around it. Btw. I think that the subnets approach will only save a significant amount of memory when the world is very large and there is a very small number of units moving around... when there's hundreds (or thousands) of units moving all over the place, you are probably going to need to have (nearly) all subnets in memory all the time. There just aren't any silver bullets in game development, but that's what keeps things interesting, isn't it .Jim Offerman Crevace Games www.crevace.com |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 6/4/2003 7:51:21 AM |
||||
| Hi Superpig, your article is very interesting but I think you make a mistake when you trade memory for speed. I tested both methods: the huge precalculated table, and the minimal table ( storing only links between waypoints ) that requires a real-time route calculation. I assure you that the second option is more efficient. So I agree with Jofferman on this point. A* is VERY fast. ( much faster than what I expected. I was like you until I tried it ! ). So it's not worth sacrificing memory. I think this is the answer to the memory problem you have in the "education" paragraph. Of course, the "subnets" technique can also help, but not as much. And anyway, you can use it in both cases. So I suggest you try a to implement A* and optimize it a bit, you'll see it's worth it. You can even reduce the CPU cost by reducing the number of path calculations, which will make your ai a little slower, but that may not be noticeable. You couldn't do that kind of trick to reduce memory usage. |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
