SA-MP Forums Archive
3D Pathfinding Theories - Printable Version

+- SA-MP Forums Archive (https://sampforum.blast.hk)
+-- Forum: Other (https://sampforum.blast.hk/forumdisplay.php?fid=7)
+--- Forum: Everything and Nothing (https://sampforum.blast.hk/forumdisplay.php?fid=23)
+--- Thread: 3D Pathfinding Theories (/showthread.php?tid=604060)


3D Pathfinding Theories - Crayder - 31.03.2016

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...

Re: 3D Pathfinding Theories - BurnZ - 31.03.2016

This seems... complicated.

But I like how these things work though.

Re: 3D Pathfinding Theories - Crayder - 31.03.2016

Quote:
Originally Posted by Gamer_Z
View Post
Just create a navigation mesh of SA, It probably already exists somewhere in the game but it would be visualised like this:


You can look in the unreal engine source how that nav mesh is made and how navigating through it is done.

Your method could work for creating those meshes, probably the only way to do it without access to the SA engine.
Also, how would you navigate only roads?
Yeah this generated mesh would be more for walking around. Your GPS data would still be best for vehicles. For walking on sidewalks though, we could use an algorithm that supports weighted nodes and weight the nodes that are near the pedestrian nodes defined in gta3.img. With that, the generated paths would tend to walk mostly on sidewalks, but if the destination was somewhere else the path would go off the sidewalk. Like say the target was across the street, the path would go along the sidewalk until crossing the street was optimal then it would cross the street.

EDIT: So anyways, I've been running my method in PAWN on my already shitty computer. And damn is it slow... It has been running for hours on just a 62.5x62.5 area (so 125x125 points, each with at least one node and a lot with multiple level nodes). The getting the nodes (on all levels) part is quick (2 seconds everytime), scanning for connections is what is slowing it down so much. Obviously it'd be a lot quicker in a plugin and on a better PC (seriously, this needs more than just a 1.55ghz single core CPU, burning 100% constantly at the moment).

Re: 3D Pathfinding Theories - Crayder - 04.04.2016

Anyways, I've applied this in PAWN and it took 5 and a half hours to run on a 125x125 unit area.

The things to note about this timing are - 1, I'm using the shittiest computer I've touched in the past decade... and 2, it's in PAWN, which as we all know, is pretty damn limited. The script was taking ALL of my 1.55 GHZ single core CPU the entire time it was running, so it could've obviously went a lot faster with an upgraded PC.

Interesting facts:
- Running at this speed, the entire SA map would take 576 days to complete.
- Exporting in my test database format, the entire SA map would occupy well over 9 gigabytes.

If you guys want to see the map I used to test this, here it is:
pawn Code:
CreateObject(19552, 0.00000, 0.00000, 50.00000,   0.00000, 0.00000, 0.00000);
CreateObject(19445, 0.00000, 0.00000, 51.50000,   0.00000, 0.00000, 0.00000);
CreateObject(19445, 0.00000, 0.00000, 55.00000,   0.00000, 0.00000, 0.00000);
CreateObject(19445, -9.00000, 0.00000, 51.50000,   -30.00000, 90.00000, 90.00000);
CreateObject(19445, -4.25000, 0.00000, 54.25000,   -30.00000, 90.00000, 90.00000);
CreateObject(19445, 4.75000, 0.00000, 56.75000,   0.00000, 90.00000, 90.00000);
CreateObject(19445, 11.25000, -3.00000, 56.75000,   0.00000, 90.00000, 0.00000);
CreateObject(19445, 11.25000, -12.75000, 56.75000,   0.00000, 90.00000, 0.00000);
CreateObject(19445, 11.25000, -21.75000, 54.25000,   30.00000, 90.00000, 0.00000);
CreateObject(19445, 11.25000, -25.75000, 52.00000,   30.00000, 90.00000, 0.00000);
CreateObject(19445, 0.00000, -9.75000, 55.00000,   0.00000, 0.00000, 0.00000);
CreateObject(19445, 0.00000, -9.75000, 51.50000,   0.00000, 0.00000, 0.00000);
CreateObject(19383, 0.00000, -16.25000, 51.50000,   0.00000, 0.00000, 0.00000);
CreateObject(19383, 0.00000, -19.50000, 51.50000,   0.00000, 0.00000, 0.00000);
CreateObject(19383, 0.00000, -16.25000, 55.00000,   0.00000, 0.00000, 0.00000);
CreateObject(19445, 1.75000, -19.50000, 53.25000,   0.00000, 90.00000, 0.00000);
CreateObject(19445, -4.25000, -16.25000, 50.75000,   -30.00000, 90.00000, 90.00000);
CreateObject(19445, 1.75000, -26.25000, 49.00000,   65.00000, 90.00000, 0.00000);
CreateObject(19445, 1.75000, -12.25000, 49.25000,   -60.00000, 90.00000, 0.00000);
CreateObject(19744, -3.00000, -38.00000, 51.72330,   0.00000, 0.00000, 171.00000);
CreateObject(19445, 2.25000, -34.00000, 52.50000,   0.00000, 90.00000, -90.00000);
CreateObject(19901, 32.12160, -10.67660, 47.21160,   0.00000, 0.00000, 90.00000);
CreateObject(19901, 47.26840, -10.35530, 49.21160,   0.00000, 0.00000, 90.00000);
CreateObject(8947, -20.98240, 23.64280, 52.97740,   0.00000, 0.00000, 0.00000);
CreateObject(19445, -25.00000, 7.25000, 53.50000,   30.00000, 90.00000, 0.00000);
CreateObject(19445, -25.00000, 4.75000, 52.00000,   30.00000, 90.00000, 0.00000);
CreateObject(19790, -20.00000, -20.00000, 50.00000,   0.00000, 0.00000, 0.00000);
CreateObject(19790, -20.00000, -13.00000, 50.00000,   0.00000, 0.00000, 0.00000);
CreateObject(19790, -27.00000, -16.50000, 50.00000,   0.00000, 0.00000, 0.00000);
CreateObject(19426, -20.00000, -16.50000, 54.75000,   0.00000, 90.00000, 90.00000);
CreateObject(19445, -20.03196, -26.55408, 52.50000,   30.00000, 90.00000, 0.00000);
And for the code that represents the test (which btw was thrown together in less than half an hour since I had shit to do in the day ahead):
pawn Code:
#include a_samp
#include colandreas
#include RouteConnector

enum node_info {
    id,

    bool:isNode,

    Float:X, Float:Y, Float:Z,
    Float:NX, Float:NY, Float:NZ,
    Connection[5]
}
new Nodes[100000][node_info];

new count, connectcount, Float:tmp;

main() {
    CA_CreateObject(19552, 0.00000, 0.00000, 50.00000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19445, 0.00000, 0.00000, 51.50000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19445, 0.00000, 0.00000, 55.00000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19445, -9.00000, 0.00000, 51.50000,   -30.00000, 90.00000, 90.00000);
    CA_CreateObject(19445, -4.25000, 0.00000, 54.25000,   -30.00000, 90.00000, 90.00000);
    CA_CreateObject(19445, 4.75000, 0.00000, 56.75000,   0.00000, 90.00000, 90.00000);
    CA_CreateObject(19445, 11.25000, -3.00000, 56.75000,   0.00000, 90.00000, 0.00000);
    CA_CreateObject(19445, 11.25000, -12.75000, 56.75000,   0.00000, 90.00000, 0.00000);
    CA_CreateObject(19445, 11.25000, -21.75000, 54.25000,   30.00000, 90.00000, 0.00000);
    CA_CreateObject(19445, 11.25000, -25.75000, 52.00000,   30.00000, 90.00000, 0.00000);
    CA_CreateObject(19445, 0.00000, -9.75000, 55.00000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19445, 0.00000, -9.75000, 51.50000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19383, 0.00000, -16.25000, 51.50000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19383, 0.00000, -19.50000, 51.50000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19383, 0.00000, -16.25000, 55.00000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19445, 1.75000, -19.50000, 53.25000,   0.00000, 90.00000, 0.00000);
    CA_CreateObject(19445, -4.25000, -16.25000, 50.75000,   -30.00000, 90.00000, 90.00000);
    CA_CreateObject(19445, 1.75000, -26.25000, 49.00000,   65.00000, 90.00000, 0.00000);
    CA_CreateObject(19445, 1.75000, -12.25000, 49.25000,   -60.00000, 90.00000, 0.00000);
    CA_CreateObject(19744, -3.00000, -38.00000, 51.72330,   0.00000, 0.00000, 171.00000);
    CA_CreateObject(19445, 2.25000, -34.00000, 52.50000,   0.00000, 90.00000, -90.00000);
    CA_CreateObject(19901, 32.12160, -10.67660, 47.21160,   0.00000, 0.00000, 90.00000);
    CA_CreateObject(19901, 47.26840, -10.35530, 49.21160,   0.00000, 0.00000, 90.00000);
    CA_CreateObject(8947, -20.98240, 23.64280, 52.97740,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19445, -25.00000, 7.25000, 53.50000,   30.00000, 90.00000, 0.00000);
    CA_CreateObject(19445, -25.00000, 4.75000, 52.00000,   30.00000, 90.00000, 0.00000);
    CA_CreateObject(19790, -20.00000, -20.00000, 50.00000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19790, -20.00000, -13.00000, 50.00000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19790, -27.00000, -16.50000, 50.00000,   0.00000, 0.00000, 0.00000);
    CA_CreateObject(19426, -20.00000, -16.50000, 54.75000,   0.00000, 90.00000, 90.00000);
    CA_CreateObject(19445, -20.03196, -26.55408, 52.50000,   30.00000, 90.00000, 0.00000);

    for(new i; i < 100000; i++) {
        Nodes[i][isNode] = false;
        
        for(new c; c < 5; c++)
            Nodes[i][Connection][c] = -1;
    }
    
    /*new time = gettime();
    ScanArea();
    printf("Nodes: %i, Time taken to scan: %i", count, gettime() - time);
    
    time = gettime();
    ScanConnections();
    printf("connections: %i, Time taken to connect: %i", connectcount, gettime() - time);
    
    time = gettime();
    PrintNodes("nodes.dat");
    printf("Time taken to save: %i", gettime() - time);*/
}

ScanArea() {
    for(new Float:x = -62.5; x < 62.5; x += 0.5) {
        for(new Float:y = -62.5; y < 62.5; y += 0.5) {
            ScanPoint(x, y);
        }
    }
}

ScanPoint(Float:x, Float:y) {
    new Float:cX, Float:nX,
        Float:cY, Float:nY,
        Float:cZ, Float:nZ;
    
    new Float:cH = 80.0;
    
    while(CA_RayCastLineNormal(x, y, cH, x, y, 40.0, cX, cY, cZ, nX, nY, nZ)) {
        if(acos(nZ) <= 63.5) {
            if(cH == 80.0 || !CA_RayCastLine(cX, cY, cZ + 0.01, cX, cY, cZ + 2.25, tmp, tmp, tmp)) {
                Nodes[count][X] = cX;
                Nodes[count][Y] = cY;
                Nodes[count][Z] = cZ;
                
                Nodes[count][NX] = nX;
                Nodes[count][NY] = nY;
                Nodes[count][NZ] = nZ;
                
                count++;
            }
        }
        
        cH = cZ - 0.01;
    }
}

ScanConnections() {
    for(new node; node < count; node++) {
        Nodes[node][Connection] = GetNodeConnections(node);
    }
}

#define Distance(%0,%1) \
    VectorSize(Nodes[%0][X] - Nodes[%1][X], Nodes[%0][Y] - Nodes[%1][Y], Nodes[%0][Z] - Nodes[%1][Z])

#define ClearPath(%0,%1) \
    !CA_RayCastLine ((Nodes[%0][X] + Nodes[%0][NX]), (Nodes[%0][Y] + Nodes[%0][NY]), (Nodes[%0][Z] + Nodes[%0][NZ]),\
        (Nodes[%1][X] + Nodes[%1][NX]), (Nodes[%1][Y] + Nodes[%1][NY]), (Nodes[%1][Z] + Nodes[%1][NZ]), tmp, tmp, tmp)

GetNodeConnections(node1) {
    new ccount, connects[5];
    
    for(new node2; node2 < count; node2++) {
        new bool:alreadyConnected = false;
    
        for(new i; i < 5; i++) {
            if(Nodes[node1][Connection][i] == node2 || Nodes[node2][Connection][i] == node1)
                alreadyConnected = true;
        }
        
        if(alreadyConnected)
            continue;
        
        if(Distance(node1, node2) < 1.42) { // 1.74
            if(ClearPath(node1, node2)) {
                Nodes[node1][isNode] = true;
                Nodes[node2][isNode] = true;
            
                connects[ccount] = node2;
                ccount++;
                
                if(ccount == 5)
                    break;
            }
        }
    }
    
    connectcount += ccount;
    
    return connects;
}

#include strlib

PrintNodes(fname[]) {
    new File:file = fopen(fname, io_append);
    
    for(new node; node < count; node++) {
        if(Nodes[node][isNode]) {
            fwrite(file,
                sprintf(
                    "%i | %.2f %.2f %.2f | %i %i %i %i %i\n",
                    node,
                    Nodes[node][X], Nodes[node][Y], Nodes[node][Z],
                    Nodes[node][Connection][0],
                    Nodes[node][Connection][1],
                    Nodes[node][Connection][2],
                    Nodes[node][Connection][3],
                    Nodes[node][Connection][4]
                )
            );
        }
    }
    
    fclose(file);
}
This is obviously going to need to be simplified a lot.