31.03.2016, 04:32
(
Last edited by Crayder; 31/03/2016 at 06:28 AM.
)
Ok, we need an efficient pathfinding system. I have a few ideas I'd like to jot down and I'd like to see what ideas you all have.
My current method theory:
This would use ColAndreas. This would require some dense, extensive ray casting. It would need to generate a super efficient node database that can be used in a plugin. Note that this method would work for custom maps.
The area is 12000x12000, each half unit in SA.
Each of these points will be tested using CA_RayCastLineNormal.
Many of these points have multiple levels (bridges, certain buildings, etc), so we will have to do multiple rays.
The first ray will be from just above Chiliad (around 700) to just below the bottom of the quarry (note sure, so let's just say -100). If this ray collides something other than water we've found a plausible node.
Now we use the normal's Z to determine if the slope of this point is below 63.5 degrees (the SA walkable slope limit) (to do so use acos on it), and if it is we will consider this a potential node for now.
Now we need to continue casting downward, but everything below this node will be a bit more complicated. Each point below this must be at least ~2.1 units below the one before it. Some of these points may not be the outside of an object so this is where the surface normal comes in again. As long as the normal's Z is positive we have potential, so we will use CA_RayCastLine from the surface to 2.1 units above it to see if a player would fit there, if so consider this a potential node for now.
Once we scanned each of these points all the way down to -100, we can start trying to connect these potential nodes.
We start with the normal of the corner node (since the normal is a normalized value it will always be 1 unit away from the ground point there. Cast a ray with CA_RayCastLine from this normal (added to the ground point obviously) to the normal of the points around it (no matter the level, just within say a 1.42 radius sphere and not on the same point). If this ray collides anything, these nodes can't be connected. Otherwise, connect them (not the normals, the nodes on the surface). Allow only a certain number of connections, at least 8. Note that the angle between the nodes doesn't really matter since we already know the surface slope of each node is below 63.5.
Now we need a database format a plugin can read. Each node will be defined as it's found index (the number of nodes found before it, the first node will be 0) and it's surface point. Then all of their connections will be defined as the found index of point A to the found index of point B. Note this should include the vice versa of each connection since each was scanned, that's fine. The plugin would be similar to Gamer_Z's RouteConnector (hell, we could probably use that plugin as a base for this one but instead of settings nodes in pawn we will directly read the database).
There would probably be more factors to determining the potential nodes, this is just what came to my head and I had to write down before I forgot. There is a bit more to the thought but this is the base.
Now please, what are your opinions on this method? What would you add to it or remove from it? What would be YOUR method?
EDIT: I'm going to develop a test for my method in the meantime...
EDIT: This would obviously take years in PAWN, perhaps a temporary version of the ColAndreas plugin itself will do since I need access to it's functions.
EDIT: Hell this would take years in almost any language...
My current method theory:
This would use ColAndreas. This would require some dense, extensive ray casting. It would need to generate a super efficient node database that can be used in a plugin. Note that this method would work for custom maps.
The area is 12000x12000, each half unit in SA.
Each of these points will be tested using CA_RayCastLineNormal.
Many of these points have multiple levels (bridges, certain buildings, etc), so we will have to do multiple rays.
The first ray will be from just above Chiliad (around 700) to just below the bottom of the quarry (note sure, so let's just say -100). If this ray collides something other than water we've found a plausible node.
Now we use the normal's Z to determine if the slope of this point is below 63.5 degrees (the SA walkable slope limit) (to do so use acos on it), and if it is we will consider this a potential node for now.
Now we need to continue casting downward, but everything below this node will be a bit more complicated. Each point below this must be at least ~2.1 units below the one before it. Some of these points may not be the outside of an object so this is where the surface normal comes in again. As long as the normal's Z is positive we have potential, so we will use CA_RayCastLine from the surface to 2.1 units above it to see if a player would fit there, if so consider this a potential node for now.
Once we scanned each of these points all the way down to -100, we can start trying to connect these potential nodes.
We start with the normal of the corner node (since the normal is a normalized value it will always be 1 unit away from the ground point there. Cast a ray with CA_RayCastLine from this normal (added to the ground point obviously) to the normal of the points around it (no matter the level, just within say a 1.42 radius sphere and not on the same point). If this ray collides anything, these nodes can't be connected. Otherwise, connect them (not the normals, the nodes on the surface). Allow only a certain number of connections, at least 8. Note that the angle between the nodes doesn't really matter since we already know the surface slope of each node is below 63.5.
Now we need a database format a plugin can read. Each node will be defined as it's found index (the number of nodes found before it, the first node will be 0) and it's surface point. Then all of their connections will be defined as the found index of point A to the found index of point B. Note this should include the vice versa of each connection since each was scanned, that's fine. The plugin would be similar to Gamer_Z's RouteConnector (hell, we could probably use that plugin as a base for this one but instead of settings nodes in pawn we will directly read the database).
There would probably be more factors to determining the potential nodes, this is just what came to my head and I had to write down before I forgot. There is a bit more to the thought but this is the base.
Now please, what are your opinions on this method? What would you add to it or remove from it? What would be YOUR method?
EDIT: I'm going to develop a test for my method in the meantime...
EDIT: This would obviously take years in PAWN, perhaps a temporary version of the ColAndreas plugin itself will do since I need access to it's functions.
EDIT: Hell this would take years in almost any language...
