Ok, so I'm really new to AI. But I'm trying to develop an engine much like SHining Forces. The problem I'm going to be facing soon is monster AI. Take a look at this screenshot so maybe you will understand better. http://www.freewebs.com/theprophecyseries/example.gif Pretend that the character is a monster. Now pretend there is that monsters target on the other side of the bush. How would I go about making the monster travel around the bush instead of just trying to walk into it? I'm designing the game in VB and I know very little c++, so if you could either describe it in psuedocode or simple c/c++, that would be awesome. Thank you :) I hope I explained it well enough.

Wow looks pretty cool.

You're probably after FOV (field of view alg) can the monster see the player?
Or a path finding algorithm the path the monster should take to the player.


Yet Another Fast FOV (from the rogue-like newsgroup)

Dijkstras shortest path algorithm is a simple path finding alg and still pretty good

A terse description of the A* path finding alg

No, there is no FOV. I'm just looking for a pathfinding technique.

I've downloaded a couple source examples to look at the different ways, but they are all huge garbled pieces of code. I don't even know where to start to understand what the code is all about. Any help? If the code is complicated I'm looking for something VB based. :)

And thanks Balaam

edit: Also, the monster may not be able to complete the whole move in one turn.

The simplest method to find the shortest path is as follows:

Let Q be an empty queue
Add the current position of the monster to the queue, and set its predecessor to null
while Q is not empty

remove position x from the queue
mark x as visited
for each position y adjacent to x

if y is the destination, set its predecessor to x, and you can now follow the trail of predecessors back to the starting position to get the path, and we're done

if y is a valid space to move to and it has not been visited, add it to the queue, and set its predecessor to x

end for

end while

if the destination was never reached in the while loop, it must be unreachable


This algorithm is called breadth first search.

oops, I made a mistake in that pseudocode. a position should be marked as visited when it is added to the queue.

I'm quite familiar with the shining force series. When building up possible walkable locations you simply branch out from the source location based on movement distance and exclude unwalkable paths. Once your tree is made the unit can select a target within that walkable tree and it'll already know how to walk there. You have to consider flying units and walking units differently however since flying units can fly over regions walking units can't.