The green polygons are obstacles on the map, the green lines I can make easily enough. The red circles represent the actor and its destination. At the start of the level I presume I need to generate the black lines between the black nodes, however, I only want the black lines to go to any visible nodes, not ones obscured by obstacles, how would I check for this? I guess I could make the links manually, but that would be a wee bit tedious.
Then when I want an actor (red dot) to move to another position (other red dot), I presume I would need to add links corresponding to the possible nodes they could move to (purple lines), but the previous issue still applies, how do I check which nodes I can go to? Once all the links are in play I guess the path (thick grey line) should be easy enough to calculate.
Also, is this a good approach to take? It seemed pretty logical to me at the time, but if there's a better way to do things then I'd like to investigate.
Thanks. =)
[Edited by - DeathCarrot on August 9, 2007 6:44:33 AM]
A* question
Author
I'm going to be making a 3D game (SDL/OGL) in which I have AI "somethings" (undecided at the time of writing) moving around a map with obstacles and walls and things, I don't know much about game development (I've yet to make anything but simple experiments) but I'd imagine A* is the way to go for this one. I need some help in generating links between nodes; here's a diagram which will hopefully help explain the thing better:
The green polygons are obstacles on the map, the green lines I can make easily enough. The red circles represent the actor and its destination. At the start of the level I presume I need to generate the black lines between the black nodes, however, I only want the black lines to go to any visible nodes, not ones obscured by obstacles, how would I check for this? I guess I could make the links manually, but that would be a wee bit tedious.
Then when I want an actor (red dot) to move to another position (other red dot), I presume I would need to add links corresponding to the possible nodes they could move to (purple lines), but the previous issue still applies, how do I check which nodes I can go to? Once all the links are in play I guess the path (thick grey line) should be easy enough to calculate.
Also, is this a good approach to take? It seemed pretty logical to me at the time, but if there's a better way to do things then I'd like to investigate.
Thanks. =)
[Edited by - DeathCarrot on August 9, 2007 6:44:33 AM]
The green polygons are obstacles on the map, the green lines I can make easily enough. The red circles represent the actor and its destination. At the start of the level I presume I need to generate the black lines between the black nodes, however, I only want the black lines to go to any visible nodes, not ones obscured by obstacles, how would I check for this? I guess I could make the links manually, but that would be a wee bit tedious.
Then when I want an actor (red dot) to move to another position (other red dot), I presume I would need to add links corresponding to the possible nodes they could move to (purple lines), but the previous issue still applies, how do I check which nodes I can go to? Once all the links are in play I guess the path (thick grey line) should be easy enough to calculate.
Also, is this a good approach to take? It seemed pretty logical to me at the time, but if there's a better way to do things then I'd like to investigate.
Thanks. =)
[Edited by - DeathCarrot on August 9, 2007 6:44:33 AM]
In theory, you cast out all rays to every possible corner, and then cull those which intersect obstacles. This is possible when precompiling the map, but not advised.
A better approach is to use occlusion: for every obstacle edge, compute the "invisibility cone" that goes out from that edge (if you prefer, the shadow that would be cast by the edge if there was a light at the starting point) and eliminate all points in the scene which fall within that cone (as well as any obstacle edges fully within that cone as well). You may use a partitioning scheme, such as a quadtree, to optimize this in order to eliminate large chunks at a time (if you start with obstacles very close to the visibility point, you should eliminate 60% of your scene in a handful of comparisons.The remaining points are those which are visible, and should thus be linked.
A better approach is to use occlusion: for every obstacle edge, compute the "invisibility cone" that goes out from that edge (if you prefer, the shadow that would be cast by the edge if there was a light at the starting point) and eliminate all points in the scene which fall within that cone (as well as any obstacle edges fully within that cone as well). You may use a partitioning scheme, such as a quadtree, to optimize this in order to eliminate large chunks at a time (if you start with obstacles very close to the visibility point, you should eliminate 60% of your scene in a handful of comparisons.The remaining points are those which are visible, and should thus be linked.
Author
OK, I looked into it, and I'm sorry to say I'm still completely lost - I understand what you're getting at with the occlusion business, I've looked at a couple of tutorials and articles which seemed relevant, but I still don't understand how I can compute the "invisibility cone" (I'm still new at this).
Also, what would be the best way to check whether an object/polygon/edge was intersecting a line/ray? I can imagine checking every edge for an intersection every time a node is checked is probably not the best way. I know I can eliminate half of the edges by pre-calculating normals for the edges and doing a dot product to see if it's facing towards or away from the node, but that's as far as I get...
Thanks.
Also, what would be the best way to check whether an object/polygon/edge was intersecting a line/ray? I can imagine checking every edge for an intersection every time a node is checked is probably not the best way. I know I can eliminate half of the edges by pre-calculating normals for the edges and doing a dot product to see if it's facing towards or away from the node, but that's as far as I get...
Thanks.
Look in the AI game programming Wisdom series of books (or the web!) for articles about Navigation Mesh (Navmesh) generation. The one in the 3rd book is quite good IMO, tho I see there are several articles about this comming in the 4th book.
There is also the Point of Visibility (PoV) approach, which is what PathEngine use I believe. Personally, I prefer navmeshes.
There is also the Point of Visibility (PoV) approach, which is what PathEngine use I believe. Personally, I prefer navmeshes.
Quote:Original post by DeathCarrot
OK, I looked into it, and I'm sorry to say I'm still completely lost - I understand what you're getting at with the occlusion business, I've looked at a couple of tutorials and articles which seemed relevant, but I still don't understand how I can compute the "invisibility cone" (I'm still new at this).
Consider the triangle ABC, where A is your currently examined point and BC is your currently examined edge. An object (point or edge) is inside the invisibility cone if and only if:
- It is on the same side of AB as C
- It is on the same side of AC as B
- It is not on the same side of BC as A
How exactly is that a 'better' approach than a simple line test to see if lines between waypoints cross obstacle lines?
Quote:Original post by DrEvil
How exactly is that a 'better' approach than a simple line test to see if lines between waypoints cross obstacle lines?
Quote:Original post by ToohrVyk
You may use a partitioning scheme, such as a quadtree, to optimize this in order to eliminate large chunks at a time (if you start with obstacles very close to the visibility point, you should eliminate 60% of your scene in a handful of comparisons).
Right, but it's significant extra work when the savings he's likely going to see may be insignificant. A brute force line test method is a more than suitable option as well. I could be wrong, as he didn't specify either way he was planning to use large numbers of obstacles or total vertices. Just thought it a bit premature to call the much simpler method 'not advised' when the little information provided in the request seems to imply(to me) the target usage is likely on the simpler side. No biggie.
Agreed, a straightforward approach would work if there were ~200 vertices on the scene. For large numbers of vertices, I believe it would become a bit too long (around 250 million edge-ray tests for 1000 vertices).
This problem falls under the broader problem of skeletonisation ('skeletonization' for our non-standard English writers... check both spellings if searching online).
As has been mentioned, point-to-point visibility tests are viable in real time only for small scenes. That is why pathing graphs based on visibility techniques are almost always computed offline at design time.
For much larger scenes with many thousands to millions of vertices, you might consider using a random tree approach... or look into the skeletonisation techniques commonly used in mobile robotics.
Cheers,
Timkin
As has been mentioned, point-to-point visibility tests are viable in real time only for small scenes. That is why pathing graphs based on visibility techniques are almost always computed offline at design time.
For much larger scenes with many thousands to millions of vertices, you might consider using a random tree approach... or look into the skeletonisation techniques commonly used in mobile robotics.
Cheers,
Timkin
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
