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

[kornwaretm]

provicio for the excelent job

[Halifax]

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.

[JP]

That does sound like a good idea actually! Consider it noted!

[christianclavet]

Hi, JP and Halifax.

Yes this could be a wonderful idea. If this can be implemented, consider putting a "boolean" to activate the curvature. So it could be used for many uses. Not sure it would work for all situations.

On another subject, Have other ideas...

Do you still think it would be possible for the AI to have dynamic waypoints? (create the waypoints with the position of the node (player or other NPC) in attack mode) This could also be used to create squad movement.

So you create a "chief" then the other NPC will follow it. We could even put in the AI directional vectors (The NPC will have to check for wall/NPC collision and replace itselft)

[dlangdev]

interesting idea, halifax.

i was looking into this last night and stumbled into prim's algorithm( see http://en.wikipedia.org/wiki/Prim's_algorithm ).

i'm still looking into this algorithm, not sure when i'll be done, but it looks like i can implement a design like what you mentioned using prim's.

with random points scattered all over the place, the prim code will figure the waypoints on-the-fly. the end-point is basically the target.

i'm also looking into qhull for subdivision of waypoints. it's too much information coming at me, i'll sort this out later.

see: http://en.wikipedia.org/wiki/Jump-and-Walk_algorithm

i think with this code, i could implement bots that dodge things thrown at them, and they can hide behind structures for protection. but that's too futuristic, though. i'll start with simple straight line attack first demo.

[Halifax]

Hi, JP and Halifax.

Yes this could be a wonderful idea. If this can be implemented, consider putting a "boolean" to activate the curvature. So it could be used for many uses. Not sure it would work for all situations.

On another subject, Have other ideas...

Do you still think it would be possible for the AI to have dynamic waypoints? (create the waypoints with the position of the node (player or other NPC) in attack mode) This could also be used to create squad movement.

So you create a "chief" then the other NPC will follow it. We could even put in the AI directional vectors (The NPC will have to check for wall/NPC collision and replace itselft)

Ah, yes that would be a great idea, the only thing is would you just want that point as a reference, as in that it isn't connected to any other points so the AI goes until it fails, or would you also want the waypoint to be dynamically connected to others?

I think this would be a great idea if you could create them in realtime dynamically.

interesting idea, halifax.

i was looking into this last night and stumbled into prim's algorithm( see http://en.wikipedia.org/wiki/Prim's_algorithm ).

i'm still looking into this algorithm, not sure when i'll be done, but it looks like i can implement a design like what you mentioned using prim's.

with random points scattered all over the place, the prim code will figure the waypoints on-the-fly. the end-point is basically the target.

i'm also looking into qhull for subdivision of waypoints. it's too much information coming at me, i'll sort this out later.

see: http://en.wikipedia.org/wiki/Jump-and-Walk_algorithm

i think with this code, i could implement bots that dodge things thrown at them, and they can hide behind structures for protection. but that's too futuristic, though. i'll start with simple straight line attack first demo.

Yeah, I checked out those wikis, those look like pretty good algorithms.

@JP:

In general, do you know what any kind of cap number would be for the number of waypoints in a scene or the number of paths connected to any one given waypoint? (To keep it realtime generally)

[JP]

To be perfectly honest no...

And i guess it's safe to say that the larger the number the slower the search is likely to be and lags could occur...

And to be honest at the moment i've seen some lags i think if you add too many NPCs... which isn't something i saw in my Java irrlicht project which used basically the same code.. so that's interesting...

But it's early days and there's still much to be done and progress has been slow so far even though a lot of time has passed as i don't have much time to work on it. So these problems should get sorted out eventually and not be a problem in general.

I used grid based searching in the java project, not waypoints, though the idea is basically the same, so i can't think why the C++ version is slower at times, should be faster than java... when i get time i'll do some comparisons and such!

[Ico]

Couldn't give it a try yet but what I don't like right now is the need to set up your own connections. How about being able to call a method like "CreatePaths(ISceneNode blockingscenenodes = NULL, vector3df MaxDistance(0,0,0))" that will iterate through all waypoints and try to connect each one with all others. Before creating a link it will perform up to two checks:
First, check the distance against the given vector (each coordinate taken as a separate distance or making some kind of deformed globe that should contain the target. (0,0,0) disables this check.
If the first check didn't fail, casts a ray from the current node to the target node. If it doesn't hit a scene node under "blockingscenenodes" (which is just some parent scene node, for example the root scene node or NULL to avoid checks) save the link/path.
Then continue with the next waypoint.
This could then be called upon loading the scene/level or within the editor.

Using a similar method might even enable waypoint generation on the fly - just removing existing paths containing the source waypoint first and the nrecalculating those for that waypoint only.

[Dorth]

Argh, that'd be deadly. You should weed out waypoints that have the same link in 2 steps instead. (like on a straight line)

also, imgaine a huge mesh of waypoint and 2 on opposite sides. You'll probably want to invoke the waypoint logic anywhere before the other side.

[Halifax]

Couldn't give it a try yet but what I don't like right now is the need to set up your own connections. How about being able to call a method like "CreatePaths(ISceneNode blockingscenenodes = NULL, vector3df MaxDistance(0,0,0))" that will iterate through all waypoints and try to connect each one with all others. Before creating a link it will perform up to two checks:
First, check the distance against the given vector (each coordinate taken as a separate distance or making some kind of deformed globe that should contain the target. (0,0,0) disables this check.
If the first check didn't fail, casts a ray from the current node to the target node. If it doesn't hit a scene node under "blockingscenenodes" (which is just some parent scene node, for example the root scene node or NULL to avoid checks) save the link/path.
Then continue with the next waypoint.
This could then be called upon loading the scene/level or within the editor.

Using a similar method might even enable waypoint generation on the fly - just removing existing paths containing the source waypoint first and the nrecalculating those for that waypoint only.

Things take time, and connecting your waypoints is just one of them. To be honest, I haven't seen any engine that doesn't require that you precalculate the paths yourself, because dynamic simply wouldn't be applicable in realtime.

[Strong99]

i think Counterstrike source comes near that idea, it calculates himself the waypoints (well not at realtime) but you don't give any waypoint yourself when you make a map/level


But you can use advanced physics (like ageia) to locate near objects and such on the fly.

If the first check didn't fail, casts a ray from the current node to the target node. If it doesn't hit a scene node under "blockingscenenodes" (which is just some parent scene node, for example the root scene node or NULL to avoid checks) save the link/path

UT3 uses that method to render visible polygons

[Ico]

Things take time, and connecting your waypoints is just one of them. To be honest, I haven't seen any engine that doesn't require that you precalculate the paths yourself, because dynamic simply wouldn't be applicable in realtime.

It doesn't have to be in realtime - at least not during the main game loop. Even some help creating waypoints in an editor would be some help. Connecting them all yourself using indizes just sounds like too much work in some situation - it really depends on map complexity etc. Improving the result and correcting errors (like too narrow gaps etc.) is ok. But setting everything up? Hm ...

My only realtime idea would be adding or moving new waypoints within the game - that would take some time but again something that doesn't have to be done in realtime/each frame.

[JP]

You're right that it would be much better and quicker for the user to have the waypoints linked up like that, it's something i tried initially but irrlicht's collision detection seemed to be a bit broken (though i'm sure i've successfully done these sorts of things before) so i couldn't get it working.

Basically the current set up is sort of an initial working version just to get things up and running, then later on, when there's time, a better version, such as ray casting, can be brought in.

Also the current version can be left available in case you'd rather define the paths yourselves.

One thing that could cause problems is this. Imagine you have a wide chasm and waypoints on either side and a bridge across the chasm. Obviously the waypoints on either side are visible to each other so with the automated approach they would link up but the waypoints should only link up over the bridge. Though you have that max distance vector idea which could solve this.... It would be good if the two methods could both be used together in an editor, like irredit so you can automatically link them all up first and then go through your map and remove and links which shouldn't be there or add in any that should.

[Ico]

You could also add invisible (or later ignored) meshes to block the chasm.

[christianclavet]

The idea I have for "dynamic waypoint creation", is this:

The dynamic waypoint is another "mode". Static waypoint are not longer accounted for. Theses waypoint are only created from 2 position: START - DESTINATION. Update of theses points are done in a specified time interval.

The difficult part to implement in this is the way the AI will deal with the environnement. (Ray intersection with the metaselector). Because it will be needed to reposition the "DESTINATION WAYPOINT" so the NPC will not go thru the walls.

- From a certain decision of the AI (ex: attack), take the current position of the NPC as a starting point, then create the destination point (for example, take the target(player) position for the first waypoint. (This is updated in time increment (start-end position), perhaps in seconds or half second (this time period could be defined)

- If the target is still in view, update the target position if the target position has changed. There will be a need to check for walls, or the NPC will find the player behind the walls, and will block there.

- If the target position is not in view, then go to the last created destination waypoint.
Then,:
- (resume to static mode) do a distance test to the static waypoints. Take the shortest route the static waypoint (collision accounted in the move). When reached; release the dynamic waypoint mode (character go back in patrol).
- do a rotate 360 degree and check if the target presence is there, and continue pursuit.

------------------------------------------------------
For a "flee" action, take the opposite direction of the target that is attacking the NPC (directional vector + specified reverse length + check for collision with the environnement), that will determine the "endpoint", and the startpoint is the current NPC position.

Some special "static" waypoint could be created as "protection" waypoint, so the NPC will check for this and "hide" behind it if damaged (again, START-DESTINATION dynamic mode). An example use would be to create a protection Waypoint near a column, so the NPC will use this to protect himself in attack and flee. Theses could be used in a RPG game when the NPC team will need to be positionned at an exact place to create an intro... etc.

More of theses types of static waypoint could be created. They are not linked to anything. They are only used if the NPC is in dynamic mode and those are used as position for special AI decisions.