irrAI 0.50 - AI module for Irrlicht [Updated 28/11/09]
dude loading data and running functions is a difference......loading data takes time and will use some ammount of your memory but running functions will use cpu-time which is something totally diffenrent.
We're programmers. Programmers are, in their hearts, architects, and the first thing they want to do when they get to a site is to bulldoze the place flat and build something grand. We're not excited by renovation:tinkering,improving,planting flower beds.
Actually the dijkstra algtm order is O((|E|+|V|) log |V|) which V will be the waypoints and E will be how many connection there are betwein this waypoints.
This is if dicjkstra is implemented with a priority queue of course, other way, it goes very high at O( |V|^2) (this would bad in runtime).
In case of and road get closed in runtime then you must recalculate ofcourse but this time is shorter due you already have the shortest way to the rest of waypoints and y can actually use some of this data, although on this last don't take my word, I don't remember exactly.
So the maximus that can happen is a O((|E|+|V|)log|V|) alghrith in runtime which is not that high. But I think (as I said) before, I think for recalculating knowing some data is very less than this. So it can be practice.
Let me find more information and let you know.
This is if dicjkstra is implemented with a priority queue of course, other way, it goes very high at O( |V|^2) (this would bad in runtime).
In case of and road get closed in runtime then you must recalculate ofcourse but this time is shorter due you already have the shortest way to the rest of waypoints and y can actually use some of this data, although on this last don't take my word, I don't remember exactly.
So the maximus that can happen is a O((|E|+|V|)log|V|) alghrith in runtime which is not that high. But I think (as I said) before, I think for recalculating knowing some data is very less than this. So it can be practice.
Let me find more information and let you know.
-
aussiedude
- Posts: 20
- Joined: Mon Feb 26, 2007 8:45 am
- Contact:
...I just finished making the new speed test. Before I had 36 Waypoints (I prefer nodes... but whatever). The new test has 625!! The results?
Well on my computer which has 512MB ram, an AMD Duron 1.2GHz processor... 7 seconds. Thats 7 seconds to go through ALL 625 waypoints, do all pathfinding calculations, then store the results. As for memory usage, those solutions for all 625 waypoints to every other 625 waypoints (390,625 solutions!) was only 10MB.
Lets see your A* do that!
I'm currently in the process of modifying the speed test to see how this goes using the realtime solving function. In theory my RTSolve() should take 1/625 of the time the normal Solve() takes, so it should be about 1 hundredth of a second
Is that ok with everyone? 10 millisecond for real time pathfinding in a map of 625 waypoints with a 1.2GHz Duron processor?
Download the Speed Test Here, source included!
Nice one for doing the speed test. 7 seconds is quite a long time for the non-realtime one but then there are a huge number of nodes, i wouldn't imagine most projects in irrlicht would need anywhere near that many, even 100 might be a large number.
Hopefully the real-time version will be as good as you suggest, that would be very nice, still not done any speed tests on my code, i should do that at some point.
Anyway, i've got an update here. It's not much of an update really, i just managed to finish off my RPG example last night. It doesn't do a huge amount with the library (though it has helped me split some stuff out and make it a bit better now) but it was fun and it was done mostly for a giggle, hope you enjoy it and if Niko sees it i'm just having a friendly joke, no one could ever really have a serious go at Niko after all he's done for us!
My plan now is to implement some chasing & fleeing stuff, hopefully with the previously mentioned dynamic waypoint system. There have been a lot of really good suggestions for improving pathfinding and such in this thread and i do plan to incorporate these at some point but i need to prioritise broadening the feature set of the library first. Basically, the pathfinding works at the moment, it's not necessarily the most realistic or whatever but it works and i'd rather have a lot of simple features that work (pathfinding, field of vision, chasing, fleeing etc) than have one really nicely implemented feature and nothing else. Once i've got the basic stuff done i'll go back over it and think about how they can be made better.
This means that if i can get the core stuff done then hopefully that will give a complete framework for the library which means Christain (and anyone else) can start using it and then the further improvements will limit the amount of work needed to update a project to a new version of the library.
Check out the first post for the new download with the RPG example included. Note that i've changed the folder structure a bit, there's now a Bin folder where the binaries go and there's a single Media folder, so now it's more like Irrlicht's folder structure which turns out is a very sensible structure!
I should also mention that the only change i made to the library the following; before the NPC code in the library would pick a new random waypoint to go to once the NPC had reached their destination. This is obviously the wrong place to put this as it should be the project using the library that decides what the NPC does when it gets to its destination. So now in the FPS example you can see a new part to the NPC callback function which deals with this.
EDIT: MasterGod; i tried to make a VC++ project for you but i just could not understand how to make a project at all in it
There didn't seem to be any options to add source files to the project or anything... I can do a VS project, is that of any use?
Hopefully the real-time version will be as good as you suggest, that would be very nice, still not done any speed tests on my code, i should do that at some point.
Anyway, i've got an update here. It's not much of an update really, i just managed to finish off my RPG example last night. It doesn't do a huge amount with the library (though it has helped me split some stuff out and make it a bit better now) but it was fun and it was done mostly for a giggle, hope you enjoy it and if Niko sees it i'm just having a friendly joke, no one could ever really have a serious go at Niko after all he's done for us!
My plan now is to implement some chasing & fleeing stuff, hopefully with the previously mentioned dynamic waypoint system. There have been a lot of really good suggestions for improving pathfinding and such in this thread and i do plan to incorporate these at some point but i need to prioritise broadening the feature set of the library first. Basically, the pathfinding works at the moment, it's not necessarily the most realistic or whatever but it works and i'd rather have a lot of simple features that work (pathfinding, field of vision, chasing, fleeing etc) than have one really nicely implemented feature and nothing else. Once i've got the basic stuff done i'll go back over it and think about how they can be made better.
This means that if i can get the core stuff done then hopefully that will give a complete framework for the library which means Christain (and anyone else) can start using it and then the further improvements will limit the amount of work needed to update a project to a new version of the library.
Check out the first post for the new download with the RPG example included. Note that i've changed the folder structure a bit, there's now a Bin folder where the binaries go and there's a single Media folder, so now it's more like Irrlicht's folder structure which turns out is a very sensible structure!
I should also mention that the only change i made to the library the following; before the NPC code in the library would pick a new random waypoint to go to once the NPC had reached their destination. This is obviously the wrong place to put this as it should be the project using the library that decides what the NPC does when it gets to its destination. So now in the FPS example you can see a new part to the NPC callback function which deals with this.
EDIT: MasterGod; i tried to make a VC++ project for you but i just could not understand how to make a project at all in it
There didn't seem to be any options to add source files to the project or anything... I can do a VS project, is that of any use?
First of all, good job on the release.JP wrote:EDIT: MasterGod; i tried to make a VC++ project for you but i just could not understand how to make a project at all in it
Second, an empty VC project?...
You just right-click the project in the solution->Add->Existing item...
Dev State: Abandoned (For now..)
Requirements Analysis Doc: ~87%
UML: ~0.5%
In the version i've got there's no option like that, which is what stumped me... I've got Visual C++ 6.0 here but i've not actually used it, i use Visual Studio .NET 2003
And i've just noticed that that's what i should be using as it's also VC++ or something... weird.. Anyway, should be able to get you a VC project later then!
And i've just noticed that that's what i should be using as it's also VC++ or something... weird.. Anyway, should be able to get you a VC project later then!
Well i had a go and the only library project i could find was 'Class Library'. This seems to produce a DLL which isn't the way i've been making the irrAI library in devcpp.
Incidentally i have no idea of the real differences between a library that's just a lib and one that's a lib and a dll... Is there any reason to choose one over the other? (i imagine there is)
I can make a PS3 library as just a lib, with no dll, but not for PC!
Incidentally i have no idea of the real differences between a library that's just a lib and one that's a lib and a dll... Is there any reason to choose one over the other? (i imagine there is)
I can make a PS3 library as just a lib, with no dll, but not for PC!
About 2003 i don't remember if it right:) (in 2005,2008 it's right) but in any case you can do it as in VC 6.0 : you must right click on <Header files> for add headers and right-click on <Source files> for add .cppMasterGod wrote:You just right-click the project in the solution->Add->Existing item...
Good luck
p.s. or in main menu->project->add existing item...
Irrlicht Engine :: DLL or static lib?JP wrote:Incidentally i have no idea of the real differences between a library that's just a lib and one that's a lib and a dll... Is there any reason to choose one over the other? (i imagine there is)
Really good explanation..
P.S
It should still be static lib in VC.. You don't even need the pro edition, EE can compile a static lib but not a dll.
Dev State: Abandoned (For now..)
Requirements Analysis Doc: ~87%
UML: ~0.5%
Last time I used VC6 was 1 year ago but if I remember right there he needs a workspace ( = Solution in later VCs)sp00n wrote:About 2003 i don't remember if it right:) (in 2005,2008 it's right) but in any case you can do it as in VC 6.0 : you must right click on <Header files> for add headers and right-click on <Source files> for add .cppMasterGod wrote:You just right-click the project in the solution->Add->Existing item...
Good luck
p.s. or in main menu->project->add existing item...
Dev State: Abandoned (For now..)
Requirements Analysis Doc: ~87%
UML: ~0.5%
-
aussiedude
- Posts: 20
- Joined: Mon Feb 26, 2007 8:45 am
- Contact:
Well I reckon 7 seconds is ok.Nice one for doing the speed test. 7 seconds is quite a long time for the non-realtime one but then there are a huge number of nodes, i wouldn't imagine most projects in irrlicht would need anywhere near that many, even 100 might be a large number.
Hopefully the real-time version will be as good as you suggest, that would be very nice, still not done any speed tests on my code, i should do that at some point.
Realtime Test App done, you can download here. Have fun. As I expected, the realtime results were near instantaneous.
I'd love to see some speed tests of your code JP, something like what i made. Just a simple iostream app, and some huge map with heaps of waypoints on it. We could both make one and race them
.Also have you considered adding Race AI and Swarm AI to this library? I could help you with the coding of it if you want. I did some notes and had some ideas on how it could be done. I'll make some tests and try it out, if it comes out ok I'll send some code your way for including in your library, if you want?
IIRC it works like this(It has been a long time since I worked on a compiler). (And by the way you can just have static libraries on PC.) But at any rate, it works like this:JP wrote:Well i had a go and the only library project i could find was 'Class Library'. This seems to produce a DLL which isn't the way i've been making the irrAI library in devcpp.
Incidentally i have no idea of the real differences between a library that's just a lib and one that's a lib and a dll... Is there any reason to choose one over the other? (i imagine there is)
I can make a PS3 library as just a lib, with no dll, but not for PC!
If you have a static library and a DLL file, I think there is a flag in the static library that tells whether it is meant to be read or it is meant to be added. And the flag is set to read when it is built for use with a DLL. Why you may ask, because you still need to know what functions are in the DLL so that it won't give you linker errors or anything like that, but it doesn't add the actual code or anything. Now if your just working with a static library, I am pretty sure it is just a compilation of all the object files (.o) that were produced from your source when building the static library. (Hence the word library, library of objcet files.)
At least that is what I have gathered to be how it works. Because if you notice, when you use just a static library it drastically raises the amount of memory your program takes up.
TheQuestion = 2B || !2B