pathfinding in 3D
Blitz3D Forums/Blitz3D Programming/pathfinding in 3D
| ||
| Does anyone have a demo and/or code for doing pathfinding in 3D? In particular a dynamic system which in which AI can navigate not only static geometry but also walk around other dynamic entities. I know I've seen a good demo with robots walking around a Maplet level but apparently I never downloaded it because I can't find it on my harddrive. ADDITION: Found it http://www.blitzbasic.co.nz/logs/userlog.php?user=1673&log=224 |
| ||
| Hi Joe, I don't know if you are interested, but I did something that was dynamic (considered other units, not just static terrain) in 2D. I never released it, though. Since it isn't 3D, you might not be interested. If you are, just let me know. |
| ||
| turtle Given the quality of your other work, I'd be interested as well ;-) |
| ||
| "Andrew Pye" did a good pathfinding demo - personally, I think it uses too many waypoints - it is in code archives somewhere. |
| ||
| Ok, I've updated the download to include a couple of collision-detection/handling pathfinders. See: http://www.blitzcoder.com/cgi-bin/showcase/showcase_showentry.pl?id=turtle177604062002002208&comments=no Look in the "more demos" folder under the Blitz Basic version. I'm actually working on some more advanced stuff these days (dynamic pathfinding, pixel-perfect pathfinding in a 'Boids' style steering environment like that described by Craig Reynolds). None of it is ready for release, though. Feedback/comments are welcome. :) |
| ||
| jhocking, I've written 3D pathfinding code based on turtle1776's 2D work. The code works similar to the 2D version. My 3D version uses realtime collision (X/Z Plane) and gravity (Y Plane) vs collision map (X/Y coords). It can support multi-tier, variable A* (4,6,8 point), and variable terrain pathfinding. Unfortunately, there is a collision bug I have yet to isolate. I believe theres a global variable conflict. I'm going to rework the pathfinding code. If I can resolve the bug, i'll post the code. |
| ||
| Hey, that sounds good. How is the pathfinding grid setup (eg. using waypoints?) And regardless of that, does your code generate the pathfinding grid automatically or does it require movement nodes placed ahead of time? In the latter case, how does one go about placing the nodes? |
| ||
| Im working ona an implementation of FMM in Blitz. Its the Best 3D Path finding and AI Avoidence system there is. For thos who dont know what FMM is. Ill give a quick list of what it does. It uses an expanding Wave front system to determine travel times from point A to point B, this means that if there is a hill that you can go over between point a and b but its high so will take a while to climb, this system will know this and calculate the fastest travel path. It always 100% of the time outputs the fastest travel path from one point to another, Where as A* can at times take routes that are not as optomized. This system has only recently been getting used in real games, as its normally used to track the flow of expanding wave fronts. like Forest fires or tidal waves and such. Even though it is slower its still possible at times to pre calc the nodes.. Anyway once im done I will post the source.. |
| ||
| turtle1776 I just tried to download your updated Astar routines but the download seems to be broken. Any possibility of having it hosted somewhere else? Cheers GrumpyOldMan |
| ||
| Hi Grumpy, just checked and it seems to be working fine. Try again? |
| ||
| jhocking I'm using the system for Bot navigation in a FPS Level. The planned implementation is to use a Point-To-Point Path Table (a Grid that stores a list of waypoints from one point to another) for path tracing, and pathfinding to handle collision avoidance. The pathfinding grid is used as realtime collision is used to check and create the path upon collision. I have developed a tool specifically for waypoint/path editing. Yavin, The FMM pathfinding system sounds very interesting. Perhaps I can employ this form of pathfinding navigating terrains. Were can I find more info? |
| ||
| Frank try searching for Fast Method Marching. You wont find anything game related on it. as I said its used to develope expanding wave front systems. Its actually only recently been used in a Pro game. Its actually AMAZING for handling Car AI. I was introduced to it after a lecture by one of Sony's Entertainments Lead Artists. on visual effects, We then had a lecture on A.I. Which covered FMM in a car game situation. I must admit it was bloody good. |
| ||
| Yavin, I found a interesting article on [a http://66.102.7.104/search?q=cache:V1t6fFRRE4cJ:cis.paisley.ac.uk/livi-ci0/livingstone_mcdowell_fmm1.pdf+Fast+Method+Marching+in+game+design&hl=en&ie=UTF-8]Fast Marching Method[/a]. |
| ||
| Yeah Daniel Livingstone is a smart guy. He's the guy who gave us the lecture on the subject, he knows his stuff when it comes to AI... Check your e-mail Frank |
| ||
| Oh yeah the powerpoint presentation is about the game side of things ;) |
| ||
| Some time ago I converted Turtles a-Star Example straight to 3D. It works nicely, but in some situations, when the path is complex, it is using too much RAM. Somebody might edit the budget of types which are used here to make this Algorithm less Memory hungry. http://www.melog.ch/dl/astar3D_2.zip |
| ||
| How to rotate an entity so it faces towards another entity? |
| ||
| you could use the PointEntity Command |
| ||
| Thank you. |
   |