Lulz for the stuck imp (flying creature)

it's still a problem after 20+ years because 0 resources are put into anything except fluffy graphics. 5 years devoted to modeling the rag doll physics and volumetric shading of individual freaking dust motes but not a second spent on keeping npcs from running into walls.

I had to take a class (required credit) on AI for Electronic Gaming. I have to say all of the choices for algorithms in the class were terrible. A* path finding is a good algorithm but you get the APE effect in the game where the ape goes over the bridge instead of the land to get to the PC. In world of warcraft some of the NPCs have a set path, some of their pathfinding is a trial and error Like a roomba. A* uses heuristic programming that allows for optimized guessing of how to get around a barrier.

I did a heuristic application of the knights tour in JAVA and I have to say it was one of the hardest things I have ever done. Both because Java is a hard game, and I had to give a value to every spot on he chess board (that meant something).

I got a bachelors in game design and I still hate most of the bassakwards stuff that makes it on the market.

http://en.wikipedia.org/wiki/Pathfinding

Cool post. A lot of those problems seem to be not so much the low-level path planning algorithm but with the slightly higher level problem of assigning costs to possible moves and giving the creatures a large enough vocabulary of moves. Or maybe some of the games are using poorly pre-computed path segments.

A* path finding is a good algorithm but you get the APE effect in the game where the ape goes over the bridge instead of the land to get to the PC.

If you have a large map, you might allow your heuristic to cheat (and thus have the potential for bad paths) - but I don't think that was the ape's problem (or the tiger's problem earlier). I think the segment they needed to cross for the direct path was simply impassible for them - meaning the roundabout path was the best route.

In fact, most of the problems in the video seemed to be bad maps/rules rather than bad algorithms. If the map says you can walk through that rock, it makes for a good path.

In some cases it has to do with invisible geometry, or geometry that the AI thinks is there but is really not there. Even in the unreal engine path finding is a difficult thing. Node path finding is another story all together, if there isn't a node there than the AI wont go that way, however attacking pathing is different.

That is why a lot online games have multyplayer and PVP, because nothing is like playing a real human. That is what AI was meant to substitute.

>> ^jmzero:
A path finding is a good algorithm but you get the APE effect in the game where the ape goes over the bridge instead of the land to get to the PC.
If you have a large map, you might allow your heuristic to cheat (and thus have the potential for bad paths) - but I don't think that was the ape's problem (or the tiger's problem earlier). I think the segment they needed to cross for the direct path was simply impassible for them - meaning the roundabout path was the best route.
In fact, most of the problems in the video seemed to be bad maps/rules rather than bad algorithms. If the map says you can walk through that rock, it makes for a good path.