phewww... now that was a job...

I'm freakin proud today...
Just finished making Dynamic pathfinding with automatic optimized node generation. The core for my A.I. Now my little babies can wander around in any scenarion possible without level maker positioning the nodes. They also can dodge objects and find multiple paths if they get stuck. They almost seem smart :)

I've been busting my ass off for a week... non-stop. (almost :)

Somehow I feel proud of having a scene with 80 dynamic objects (soft % rigid) and 30 static objects and 1000 bullets and particles (tens of thousand of collision checks per frame), Bloom filter and Dynamic pathfinding on 4 computer ships in complex level running at over 100fps on my athlon 1800xp...

... back to work.... still lot's to do.


(Image from the actual game... no postprocessing :)

Wow. That game gets better every time I look at it.
Sounds like a cool system... Should I try to get it from you by being a brown-nosing idiot, or give up now?

Looks excellent man. 2D gameplay :D Love it. Really can't wait to see this one finished :o)

This is for those interrested about the actual pathfinding...

The pathfinding is A-star used on a graph formed by nodes and connections between them. But then I dynamically alter the path structure by assigning higher costs to paths going thru dynamic objects. So the A.I. tries to dodge dynamic objects... but if a dynamic objects blocks a path to the target and no alternative paths are available and A.I really wants to get to it... it tries to push the object away or break it. The pathfinding is also calculated constantly .. so if A.I is pushed away from the calculated path it always seeks a better path. So instead going back to the nearest node of the path it was pushed away from. It calculates a new better path from it's current location. So the pathfinding is really dynamic.

Also the level maker doesn't have to build the nodemap manually. I 'boxify' the levels by filling the level with various sized boxes. This reduces the amount of nodes in open areas and makes more nodes in tight places. This is a big optimization. Less nodes equals faster pathfinding.

Also the A* itself uses binary heaps to make the processing of the open nodes faster. Also heuristic used in A* is precalculated. All in all... as much is precalculated as possible. (except the actual paths.)


[edit]



This shows the automatic node placement on a complex level.

Nice :)
How can you make sure that everything moves around in a smooth way using A*, rather than just in straight lines or diagonal lines?

Because the game's physics based approach the ships actually just follow the nodes in the current path. So they don't actually follow the exact path.. they improvise :).

They pick a node to go towards to and turn smoothly. They use steering and accelerate as needed. Just like a human player.

And btw. the A* is not necessarily used in a grid. Just like in my game... it can be used in any shaped graph...

Thanks for the insite! That's a great system. Looks like I'll have to learn about binary heaps.

One cautionary note: the background, while stunning, is making it a little difficult to discern what's an obsticle and what's just background decorations. I see you've done a soft focus on the BG but do you think going a little darker on it will help seperate it from the FG action a bit better? Or is it just me?

NEW DEMO PLEASE!!!!

Now where's the code? ;) Sounds fantastic. Hats off.

I'd see a doctor, mate - sounds bloomin' painful. What's that in anglaisee anywho?

hehe - j/k - Sounds great. Ive always liked the look of that 'nano', reminds me of The Fantastic Voyage or some documentary... good luck!

Any chance of sharing your secret? ;)

I think he just did ;p

Anyway, great work Bouncer!

That looks like it is against-the-laws-of-physics impossible. That impossible. Outstanding!

feck! I am jealous.