Posted By: LarryLaffer
Intense Pathfinding 3 - 01/26/10 17:03
Hi everyone,
I'm happy to announce yet another Intense Illusions release. Intense Pathfinding 3 is out and it's totally free. For 4 years now I've been struggling with a nice plug-n-play pathfinding solution for gamestudio. Although pathfinding is a standard feature in many engines and it's now considered a 'solved' problem in the game industry, gamestudio has always been lacking in that area and posts asking for pathfinding always pop-up in the forums.
Pathfinding is not as easy as some people may think. There's more to it than a simple search-algorithm which can be found in wikipedia and takes no more than 10 lines of code. There's the graph generator, dynamic obstacle avoidance (avoiding moving objects), 3d level support (stairs, slopes, multi-store buildings), accounting for the actor's size, and so much more. For example, most pathfinding solutions I've seen here before rely on a single c_trace to determine if an actor can walk between two waypoints (nodes) which can produce false positives or false negatives. If there's LOS (successful c_trace) there still might be a gap on the floor which would prevent an actor from walking across (unless he can fly) and if there's no LOS the obstacle that blocks the c_trace may still have been climbable (a small lump of terrain) actually allowing the actor to walk across.
I think the reason that pathfinding tools have not been very successful for gamestudio in the past (including my tools, IP1 and IP2) is the fact that middleware is really really hard to get right. Take I.P.3 for instance. Some people use blocks while others use model-only levels and others use terrain or a mix of all three. Some put the origin point of their models at the waist while others position it on the feet. Some scale their worlds at 30 quants per meter and others use 90. Some use vertex animations and others use bones. Middleware needs to interface with many aspects of the project that is being installed to, and that is generally a pain in the butt. Also, most programmers cringe to the idea of having to use code written by strangers on their own projects since it's harder to understand and debug than their own code.
With Intense Pathfinding 3 I hope to have ironed out every single one of these problems. As I've mentioned IP3 is freeware so I don't get much out of doing this. It all started 4 years ago when I released my first pathfinding code snippet only to get feedback about it not working with this case and that. So it sort of became a challenge for me to make a tool that will work for any gamestudio project and be flexible enough to fit all game genres. I wanted it to be so good that no other pathfinding tool would need to exist (not that there is any, but there used to be a couple a few years back) and people wouldn't have a reason to make their own pathfinding, except for the purpose of learning. So, as my personal vanity project I wanted to make Intense Pathfinding some sort of a de facto plugin for all pathfinding purposes in gamestudio.
And with this very long and completely unnecessary introduction I present to you Intense Pathfinding 3:
Official Page | Download Link
Features List:
* Easy 1 Click Integration (New In IP3)
* Panel System (New In IP3)
* Improved Graph Visualization (New In IP3)
* Points Of Visibility Pathfinding (node based)
* Pure Dijkstra Search Algorithm (fast)
* 999 Max Nodes per level
* 999 Max Pathfinding-Entities per level
* 999 levels per project (New In IP3)
* Obstacle Avoidance Using Repulsion Vectors (avoids other dynamic entities, without using c_traces)
* Three Dimensional (can handle floors, slopes, stairs, rough terrain, etc.)
* String Pulling (smooth paths)
* Runtime Search (handles dynamic environments like doors, bridges and demolished walls)
* Volume Raycasting (Size of entity is considered, making sure the path is wide and tall enough)
* Gravity RayCasting (Making sure there's ground below the path)
* Polygon Precise RayCasting (Supports model-only levels and terrains)
* Graph Generating Tool (automatically links nodes to each other; you just need to place them in the level)
* Written in Lite-C
* Works with all A7 editions (Trial, Extra, Commercial, or Professional)
* Debugging Tools (Visually seeing the Graph, Obstacle avoidance vectors and every c_trace made at runtime)
* Open Source. No DLLs.
* Fully documented
In a gist, you can add pathfinding to your game by using IP3 like this: You install Intense Pathfinding 3 which will put a few files in your Gstudio7 folder, like a dll that allows you to have a menu in WED for pathfinding settings, the lite-c script files, some images, models, etc. If you don't like installers, you may alternatively download this zip file and extract it to your Gstudio7 folder just like a gamestudio beta patch. Now when you open WED a new menu will appear:
You click anywhere on that menu and get a message asking you to 'enable Intense X for this project'. Don't let this message scare you. All it does is add the following line in your main script for you: "#include <IntenseX.h>". Now you won't even have to copy Intense X files to your project's folder because it will find them automatically from the Gstudio7 folder while keeping your project nice and organized.
Next, you add some waypoints to your level, as explained here, here and here. Finally, you enable Pathfinding for all the models in the level that need it:
Programmers may hate this because they'd want to manually add the pathfinding script to their model's action by code and also by doing this that actor will ignore the behavior that you've already attached to this model. Though you can easily add your own code to all actors by using these functions. It's actually easier since you now have a convenient way of identifying every actor and retrieving their pointer in lite-c by actually giving them a name:
If you're wondering how does the WED panels influence things in-game, it's very simple. I store every value you input in those panels in a sort of .ini file that I call IntenseX.dat and is located in your project's main folder. I then load up these settings into structs and variables when the game loads, and that's about it. You can even change the values directly from the .ini file if you don't want to open WED and you know what to look for.
Now you go to the Levels panel, select your wmb file and build the pathfinding graph which will look like this:
And that's about it. You can now open SED and have actors walk from anywhere to anywhere, avoiding both geometry, static models, terrains and dynamic models (other actors, barrels with physics, etc) by using this very simple command:
You can see all the interface functions provided by Intense Pathfinding 3 here.
You're also given the choice to use IP3's movement and animation code, or use your own. Just by unchecking a checkbox in the Npc panel you can completely disable IP3's subsystems and use your own. If you uncheck Movement for example, when you command an actor to move somewhere IP3 will still plot a path for the Npc but it's up to the programmer to use Intense Pathfinding output to move the Npc in the right direction every frame. Check my discussion with an Intense X user(Fear) here for instructions to do just that. The point here is that you can use and tweak IP3 any way you like without ever having to check Intense Pathfinding's source files.
Which leads me to my next and final point (btw, so sorry about this HUMONGOUS post...). I noticed that over the years as Intense Pathfinding grew more in size and complexity the less people would actually use it. IP1 didn't had panels and you had to add it manually to your project by adding include lines to your main script and copy all 3 .wdl files to your project directory. But this helped people understand exactly how my tool worked and did appreciate the simplicity. I would love nothing more than to keep it the same way for IP3 but as I had to add more features like dynamic obstacle avoidance, customizable animation system, etc, etc, this could not be the case anymore. As I explained before, you could write a simple pathfinding system in a couple of days but you will have to add necessary features to it every day to keep up with modern day standards that it will undoubtedly bloat your code in no time at all. To keep all the great features and still make a plug-n-play system I had to go with a different approach. I made this project as big as it had to be but I designed it so it wouldn't be vital for the programmer to need to actually look at the source code in order to be able to understand it and use it. You can look at it if you want to of course, but there won't be any real reason to do so. You can talk to the IP3 engine just by using the Interface functions and treat the whole system as a black box instead of a bunch of lite-c scripts filled with 3rd party code. Black boxes are necessary in order to reduce complexity and let a certain group of developers "step on it" and develop on a higher level instead of forcing everyone to learn absolutely everything in order to develop a game. As users consider gamestudio and the physics plugins as black boxes, jcl considers directX as a black box, directX developers considered c++ as a black box, and it goes on and on.
To get started with Intense Pathfinding 3 I highly recommend that you watch this video. Actually, maybe you'd like to watch it before you download it to see what this is all about:
Old Zinc Video Tutorial
In that video I call the project Zinc instead of Intense Pathfinding 3 which was an old name for it that also included a Trial of Intense Ai in it. I don't promote Intense Ai with Intense Pathfinding anymore but I kept the video since I don't want to make another one just to change the name.
Once again, sorry this post got soooooo big. Once I start talking about pathfinding I just can't seem to stop
. One last thing and I'm off. If you'd like to see Intense Pathfinding 3 embedded with WED and GED on a future version of gamestudio and you think that other people (that in all probability don't read these forums and would never hear about IP3 otherwise) might find this useful please reply here saying so. If jcl sees there's a lot of people sharing my view on this he may consider it. If this does happen, I will remove all references to Intense X on it and only keep the necessary menus that are absolutely required for IP3 to work (for example, having an item on the About menu getting you to the Intense X manual may not be completely necessary). It will probably just be a sub-menu somewhere called something subtle like "Pathfinding".
Thank you very much for going through the whole post. For any questions, please reply here. I'll be keeping a close eye on this thread for the next few days.
Cheers,
Aris
PS: For those with a shorter attention span (again, I don't blame you. I could hardly proof read the whole thing myself) just reply saying "Aye!" if you want gamestudio to come with free pathfinding!
I'm happy to announce yet another Intense Illusions release. Intense Pathfinding 3 is out and it's totally free. For 4 years now I've been struggling with a nice plug-n-play pathfinding solution for gamestudio. Although pathfinding is a standard feature in many engines and it's now considered a 'solved' problem in the game industry, gamestudio has always been lacking in that area and posts asking for pathfinding always pop-up in the forums.
Pathfinding is not as easy as some people may think. There's more to it than a simple search-algorithm which can be found in wikipedia and takes no more than 10 lines of code. There's the graph generator, dynamic obstacle avoidance (avoiding moving objects), 3d level support (stairs, slopes, multi-store buildings), accounting for the actor's size, and so much more. For example, most pathfinding solutions I've seen here before rely on a single c_trace to determine if an actor can walk between two waypoints (nodes) which can produce false positives or false negatives. If there's LOS (successful c_trace) there still might be a gap on the floor which would prevent an actor from walking across (unless he can fly) and if there's no LOS the obstacle that blocks the c_trace may still have been climbable (a small lump of terrain) actually allowing the actor to walk across.
I think the reason that pathfinding tools have not been very successful for gamestudio in the past (including my tools, IP1 and IP2) is the fact that middleware is really really hard to get right. Take I.P.3 for instance. Some people use blocks while others use model-only levels and others use terrain or a mix of all three. Some put the origin point of their models at the waist while others position it on the feet. Some scale their worlds at 30 quants per meter and others use 90. Some use vertex animations and others use bones. Middleware needs to interface with many aspects of the project that is being installed to, and that is generally a pain in the butt. Also, most programmers cringe to the idea of having to use code written by strangers on their own projects since it's harder to understand and debug than their own code.
With Intense Pathfinding 3 I hope to have ironed out every single one of these problems. As I've mentioned IP3 is freeware so I don't get much out of doing this. It all started 4 years ago when I released my first pathfinding code snippet only to get feedback about it not working with this case and that. So it sort of became a challenge for me to make a tool that will work for any gamestudio project and be flexible enough to fit all game genres. I wanted it to be so good that no other pathfinding tool would need to exist (not that there is any, but there used to be a couple a few years back) and people wouldn't have a reason to make their own pathfinding, except for the purpose of learning. So, as my personal vanity project I wanted to make Intense Pathfinding some sort of a de facto plugin for all pathfinding purposes in gamestudio.
And with this very long and completely unnecessary introduction I present to you Intense Pathfinding 3:
Official Page | Download Link
Features List:
* Easy 1 Click Integration (New In IP3)
* Panel System (New In IP3)
* Improved Graph Visualization (New In IP3)
* Points Of Visibility Pathfinding (node based)
* Pure Dijkstra Search Algorithm (fast)
* 999 Max Nodes per level
* 999 Max Pathfinding-Entities per level
* 999 levels per project (New In IP3)
* Obstacle Avoidance Using Repulsion Vectors (avoids other dynamic entities, without using c_traces)
* Three Dimensional (can handle floors, slopes, stairs, rough terrain, etc.)
* String Pulling (smooth paths)
* Runtime Search (handles dynamic environments like doors, bridges and demolished walls)
* Volume Raycasting (Size of entity is considered, making sure the path is wide and tall enough)
* Gravity RayCasting (Making sure there's ground below the path)
* Polygon Precise RayCasting (Supports model-only levels and terrains)
* Graph Generating Tool (automatically links nodes to each other; you just need to place them in the level)
* Written in Lite-C
* Works with all A7 editions (Trial, Extra, Commercial, or Professional)
* Debugging Tools (Visually seeing the Graph, Obstacle avoidance vectors and every c_trace made at runtime)
* Open Source. No DLLs.
* Fully documented
In a gist, you can add pathfinding to your game by using IP3 like this: You install Intense Pathfinding 3 which will put a few files in your Gstudio7 folder, like a dll that allows you to have a menu in WED for pathfinding settings, the lite-c script files, some images, models, etc. If you don't like installers, you may alternatively download this zip file and extract it to your Gstudio7 folder just like a gamestudio beta patch. Now when you open WED a new menu will appear:
You click anywhere on that menu and get a message asking you to 'enable Intense X for this project'. Don't let this message scare you. All it does is add the following line in your main script for you: "#include <IntenseX.h>". Now you won't even have to copy Intense X files to your project's folder because it will find them automatically from the Gstudio7 folder while keeping your project nice and organized.
Next, you add some waypoints to your level, as explained here, here and here. Finally, you enable Pathfinding for all the models in the level that need it:
Programmers may hate this because they'd want to manually add the pathfinding script to their model's action by code and also by doing this that actor will ignore the behavior that you've already attached to this model. Though you can easily add your own code to all actors by using these functions. It's actually easier since you now have a convenient way of identifying every actor and retrieving their pointer in lite-c by actually giving them a name:
Code:
you=ix_getEntity("Bob");
If you're wondering how does the WED panels influence things in-game, it's very simple. I store every value you input in those panels in a sort of .ini file that I call IntenseX.dat and is located in your project's main folder. I then load up these settings into structs and variables when the game loads, and that's about it. You can even change the values directly from the .ini file if you don't want to open WED and you know what to look for.
Now you go to the Levels panel, select your wmb file and build the pathfinding graph which will look like this:
And that's about it. You can now open SED and have actors walk from anywhere to anywhere, avoiding both geometry, static models, terrains and dynamic models (other actors, barrels with physics, etc) by using this very simple command:
Code:
ix_MoveTo("Bob",500,200,10);
You can see all the interface functions provided by Intense Pathfinding 3 here.
You're also given the choice to use IP3's movement and animation code, or use your own. Just by unchecking a checkbox in the Npc panel you can completely disable IP3's subsystems and use your own. If you uncheck Movement for example, when you command an actor to move somewhere IP3 will still plot a path for the Npc but it's up to the programmer to use Intense Pathfinding output to move the Npc in the right direction every frame. Check my discussion with an Intense X user(Fear) here for instructions to do just that. The point here is that you can use and tweak IP3 any way you like without ever having to check Intense Pathfinding's source files.
Which leads me to my next and final point (btw, so sorry about this HUMONGOUS post...). I noticed that over the years as Intense Pathfinding grew more in size and complexity the less people would actually use it. IP1 didn't had panels and you had to add it manually to your project by adding include lines to your main script and copy all 3 .wdl files to your project directory. But this helped people understand exactly how my tool worked and did appreciate the simplicity. I would love nothing more than to keep it the same way for IP3 but as I had to add more features like dynamic obstacle avoidance, customizable animation system, etc, etc, this could not be the case anymore. As I explained before, you could write a simple pathfinding system in a couple of days but you will have to add necessary features to it every day to keep up with modern day standards that it will undoubtedly bloat your code in no time at all. To keep all the great features and still make a plug-n-play system I had to go with a different approach. I made this project as big as it had to be but I designed it so it wouldn't be vital for the programmer to need to actually look at the source code in order to be able to understand it and use it. You can look at it if you want to of course, but there won't be any real reason to do so. You can talk to the IP3 engine just by using the Interface functions and treat the whole system as a black box instead of a bunch of lite-c scripts filled with 3rd party code. Black boxes are necessary in order to reduce complexity and let a certain group of developers "step on it" and develop on a higher level instead of forcing everyone to learn absolutely everything in order to develop a game. As users consider gamestudio and the physics plugins as black boxes, jcl considers directX as a black box, directX developers considered c++ as a black box, and it goes on and on.
To get started with Intense Pathfinding 3 I highly recommend that you watch this video. Actually, maybe you'd like to watch it before you download it to see what this is all about:
Old Zinc Video Tutorial
In that video I call the project Zinc instead of Intense Pathfinding 3 which was an old name for it that also included a Trial of Intense Ai in it. I don't promote Intense Ai with Intense Pathfinding anymore but I kept the video since I don't want to make another one just to change the name.
Once again, sorry this post got soooooo big. Once I start talking about pathfinding I just can't seem to stop
. One last thing and I'm off. If you'd like to see Intense Pathfinding 3 embedded with WED and GED on a future version of gamestudio and you think that other people (that in all probability don't read these forums and would never hear about IP3 otherwise) might find this useful please reply here saying so. If jcl sees there's a lot of people sharing my view on this he may consider it. If this does happen, I will remove all references to Intense X on it and only keep the necessary menus that are absolutely required for IP3 to work (for example, having an item on the About menu getting you to the Intense X manual may not be completely necessary). It will probably just be a sub-menu somewhere called something subtle like "Pathfinding".Thank you very much for going through the whole post. For any questions, please reply here. I'll be keeping a close eye on this thread for the next few days.
Cheers,
Aris
PS: For those with a shorter attention span (again, I don't blame you. I could hardly proof read the whole thing myself) just reply saying "Aye!" if you want gamestudio to come with free pathfinding!
.Thanks!
You are right with your assumption that many projects don't work out because of missing pathfinding.
contribute, thank you very much 
. 
Oh well 