irrAI 0.50 - AI module for Irrlicht [Updated 28/11/09]

[aussiedude]

Well I just finished reading this whole thread and going over most of the irrAI source files and the FPS example. GREAT WORK JP! (and others who contributed?... was there others?...)

Heres some of my thoughts:

Heh, I am back with just one more suggestion. Actually more of a pretty feature that I don't want implemented anytime soon, but just for thought.

I was browsing over some documents dealing with pathfinding and AI that were presented at a GDC, I forget the year. At any rate, the point about smooth curvical movement between waypoints makes AI looks more believable. They also presented some tech documents on how to implement it with some basic trig functions, etc.

I just think this would be a great feature, because for anyone who has ever watched the Crysis tech demo, they would see that through two waypoints they walk around a curve instead of directly to it.

That's probably my last suggestion.

I had an idea for how this could be done. I actually did something like this before, except I cheated and didn't use any trig. I was making a little 3D thingy in DarkBASIC and wanted to make a bug fly around in a smooth curved path around a certain path. What I did was I made a invisible object that followed the path exactly travelling at a speed of X and then made the bug follow the invisible object at a speed of X+(some value determined by the distance between the bug and the invisible object). Basically I made it speed up when it was getting too far away from the invisible object and slow down when it was getting too close.

The result was that the invisible object would always reach the corner first and start going along the next path. Because the bug was following it, it would slowly curve around the corner as the movement of the invisible object would slowly change the bugs rotation.

Picture for those who like to learn visually instead of through reading:


Maybe something like this could be used? Either that or you just work out a system where the waypoint the NPC is walking to and the next waypoint slowly shifts influence on the NPC's movement. Basically the same thing except with more maths... I prefer the easy way...

Also one thing I thought maybe which would be nice is changing the waypoints from being set positions to being zones? Like instead of the NPC's travelling to a the waypoints EXACT location, they instead travel to a point in that waypoints zone. It might just make the movement look a little more random and less like there is an exact path being followed by all NPC's. The size/shape of the zone could be defined as a sphere where the user can set the scale of the spheres XYZ.

Like for example in a map like this:

In this map, when the NPC's and travelling around the map between the waypoints (white circles), they could move from any point in the waypoints to any other point in the other waypoints, thus making the movement look.... um... cooler?

As for WHERE in the waypoint the NPCs go... that could be random.. or it could be based on where the next waypoint is? (so the NPC is seen trying to 'cut' corners).

Well thats my suggestions... if I can work out more about how this irrAI library works maybe I'll add this myself.

@JP: Do you mind me asking what algorithm you used (or based) your pathfinding code on? Cause I'm looking at it and I can't really figure out whats going on in it. I'd love to try and have a go at adding stuff to this project but I'm stilling trying to work out exactly how it works, when I have a better idea then I'll start adding stuff.

[JP]

That's a pretty nicely thought out trick aussiedude! I should think it's possibly cheaper as it does less maths, not sure if there'd be any added overhead for two objects or something but it sounds easier to implement too!

I also like this zones idea... it's certainly a bit unrealistic having the NPC travel between the exact same points all the time, and it means that if two NPCs want to pass each other they actually have to go through each other, with this zones idea it would probably be easier to have NPCs passing by.

The algorithm i've implemented there is just a simple breadth first search algorithm. It just gets the neighbouring waypoints to the current one and adds them to the end of a queue after checking if the current waypoint is the goal. It's easy to change it to depth first by instead adding the neighbours to the front of the queue. I do plan to implement the other search algorithms i had in my java based irrlicht project for Uni and also your dykstra (can't be bothered to check the spelling of his name ) algorithm too and then we can see which is the best performance etc.

I did do testing on them in my java project for speed and completeness (whether they found the best paths etc) so i can check back on that.

[JP]

I just had a thought about integrating dijkstra's algorithm for searching, and i'm wondering if it's a good idea...

Obviously it works, aussiedude has shown us that but it's not real time as it has to be pre-computed (does it take long to solve? any figures?) and then you use the solution to find paths.

So that's fine if your environment isn't going to change... but if, for example, some area of your map became unavailable (locked door, landslide or something) then this pathfinding wouldn't work as you'd need to be able to dynamically remove the waypoint from the system... or maybe you could update the solution from dijkstra quite quickly if you just removed a waypoint?

Obviously if there's going to be multiple search algorithms implemented then you'd be able to choose between them so i guess if you knew your environment was going to change then you'd just not use the dijkstra implementation...

Does anyone have any thoughts on this?

[aussiedude]

Well dijkstra doesn't HAVE to be realtime, I could have made my library realtime but I felt that it was in my favor to make it pre-computed. Most of the pathfinding I had planned to use this for was going to be on maps with very few nodes, with lots of NPC's and with the map staying the same. Hence it was better to have a pre-computed pathfinding solution.

Also because of the way dijkstra works, even if you want just the path from one node to one other node, you end up with the path from one starting node to EVERY other node! So it seemed a bit of a waste to me not to be using the extra paths that were being generated.

In fact changing my library to be realtime is not so hard now that I think about it:

Code: Select all

    // GREEN
    void Map::solve()
    {
        // Generate all solutions for all Nodes from every Node to every 
        // other Node
        Node * q = this->head;
        while(q!=NULL)
        {
            // Clear q for new solutions linked list
            q->deleteAllSolutions();
            
            // Do calculations for this Node
            calculateShortestPaths(q);
            
            // Generate New Linked List of Solutions
            Node * pt = this->head;
            Node * current;
            while(pt!=NULL)
            {
                // Look for the first step required to reach pt from q. 
                // Once founded addSolution() to q.
                current = pt;
                if(current!=q)
                {
                    while(current->previous!=q && current->previous!=NULL)
                    {
                        current = current->previous;
                    }
                    q->addSolution(pt,current);
                }
                else
                {
                    q->addSolution(pt,current);
                }
                
                // Go to next Node;
                pt = pt->next;
            }
            // Found all solutions for q, now go to next Node and repeat
            q = q->next;
        }
    }

This function is the main 'solve()' function called to pre-compute all the pathfinding and store it. Basically it just goes to EVERY node and does the pathfinding from that node to every other node. If I was to take out the first WHILE loop and instead change 'q' to a specific node and make the 'pt' node a specific destination node.... etc etc etc.. Then get rid of the addSolution() stuff..... etc... make it return a node pointer... etc ... very soon I could have a realtime pathfinding library. Infact I might try that later on.


As for how long it takes to solve, I've made you a simple speed test app for you to test. If you want you can edit the source of the app and add a timer if you want an exact number in milliseconds or something.

http://gradyiscool.googlepages.com/miNavSpeedTest.zip

That speed test basically makes a map of 36 nodes and connects them up, it then solves the whole map, going through each node and perform the pathfinding, storing all results it generates... for me it happens almost instantly on this computer, even if I take out the cout lines and stuff, done in a flash... No, I don't have a fast computer The processor is only an AMD duron, 1.2GHz.

Also on a surprising note, the test app uses very little memory?!

I watched the memory usage in the task manager while it ran, even after it was storing a miNav Device, a map, 36 Nodes, tonnes of connections and solutions for all the Nodes, it was only using an extra 70KB more than what it started with.

[aussiedude]

Ha! That was easier than I thought...

I've made a new function in my miNav library called RTsolve() aka realtime solve. It's like a combination of solve() and getSolution(). It takes a position and destination and returns a pointer to the next step required. The only differences is the calculation is done on the spot.

Here's the new function:

Code: Select all

    // GREEN
    Node* Map::RTsolve(Node* Position, Node* Destination)
    {    
        // Do calculations for this Node
        calculateShortestPaths(Position);
        
        // Look for the first step required to reach Destination from Position. 
        // Once founded return Node Pointer.
        Node * current = Destination;
        if(current!=Position)
        {
            while(current->previous!=Position && current->previous!=NULL)
            {
                current = current->previous;
            }
            return current;
        }
        else
        {
            return current;
        }
    } 

Well there you have it, dijkstra can be realtime too It was also really fast too, which was rather nice. Almost the same speed as the pre-computed version.

[JP]

Cool, i'll have a look at it when i get some time and see how it compares to my other algorithms!

[Dorth]

errr.... 36 nodes is like nothing in a real game. And since I highly suspect your method to be factorial, try with 100, or 1000. Doesn,t mean it won't work. But it might give a better idea ^^

[JP]

This is a good point Dorth, i should think Dijkstra's algorithm would certainly get quite slow with a larger number of nodes due to calculating for every other node... huge number of computations when you get a bigger graph....

I also need to do some testing with my current algorithms for a larger number of nodes as i think the highest i've tested is about 10 or so, which is again way too low for a proper game to use.

[sudi]

Well what kind of game are u talking about? I have not seen a FPS with more than like 64 AI players. And thats just multiplayer fps like bf. when u have a singleplayer the AI mostly nly gets activated when the player comes in range. Yeah and rts AI well thats something else. but ii guess u won't need more than 64 for now.

[Dorth]

... An Ai MOVES on the nodes, it is not the node itself. An AI could be alone on a map of 100 000 nodes...

[JP]

Yeah we should be calling them waypoints really (it's what they're called in the code anyway), not nodes because nodes are generally thought of as something to be rendered in irrlicht (nodes of the scene graph rather than nodes of a pathfinding graph as we were talking about).

[sudi]

oh i thought u where talking about the ai nodes which moves on the waypoints and updates the irrlicht nodes.

[sp00n]

Well what kind of game are u talking about? I have not seen a FPS with more than like 64 AI players. And thats just multiplayer fps like bf. when u have a singleplayer the AI mostly nly gets activated when the player comes in range. Yeah and rts AI well thats something else. but ii guess u won't need more than 64 for now.

look at the Doom 1-2 there are more than 64 monsters atm:))))
about RTS - look at the Cossacs, there is a standart solution about AI (calculate an AI not for each unit, just for the set of the units with averaged weight for the waypoint's graph-node )

[sudi]

@sp00n
but the AI for these monsters in Doom1-2 is not active the whole time.

[sp00n]

@sp00n
but the AI for these monsters in Doom1-2 is not active the whole time.

lol
did you ever seen the soutces of the Doom 1-2? )))
AI of the all monsters in the level is a part of the loaded level data to the memory. In Google we trust:)