1. SA-MP Forums Archive
  2. Other
  3. Everything and Nothing

Linear Mode
3D Pathfinding Theories
Crayder
Banned
Posts: 3,324
Threads: 96
Joined: Sep 2013
#4

04.04.2016, 16:58
( Last edited by Crayder; 04/04/2016 at 09:19 PM. )
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.
Find
Reply
« Next Oldest | Next Newest »


Messages In This Thread
3D Pathfinding Theories - by Crayder - 31.03.2016, 04:32
Re: 3D Pathfinding Theories - by BurnZ - 31.03.2016, 13:31
Re: 3D Pathfinding Theories - by Crayder - 31.03.2016, 15:00
Re: 3D Pathfinding Theories - by Crayder - 04.04.2016, 16:58

Forum Jump:


Users browsing this thread: 1 Guest(s)
  1. SA-MP Forums Archive
  2. Other
  3. Everything and Nothing