How about simple 'bread crumbs'?

That is the player drops 'virtual' crumb every few steps or change of direction. Each crumb has a timestamp and a lifespan. If the monster loses visual sight of the player they search for the nearest crumbs and travel towards the youngest (most recently dropped). This can easily be developed to allow for different monster types to be able to follow crumbs for longer or shorter durations etc.

Here's a link to an image of what the game looks like, without graphics.

The picture displays the player (blue orb) in a dungeon with an enemy orc (green orb) around the corner.

The light gray areas are walkable, the dark grey are non-walkable sprites.

No tiles or grids are used.

LINK: http://sv.tinypic.com/view.php?pic=30j0mcy&s=4

It is being developed using ActionScript 3 and Flash.

What algorithms and methods would you think would be best for this type of game?

The enemies run slightly faster than the player, so you can not out-run them, and they shouldnt be able to notice you behind obstacles and walls, unless they have already detected you, then they will follow until either of you are dead.

pto [EDIT: and jyk]'s method sounds pretty good for this.


[Edited by - Emergent on September 19, 2009 3:26:30 PM]

Quote: Original post by Ciubhran
Here's a link to an image of what the game looks like, without graphics.

The picture displays the player (blue orb) in a dungeon with an enemy orc (green orb) around the corner.

The light gray areas are walkable, the dark grey are non-walkable sprites.

No tiles or grids are used.

LINK: http://sv.tinypic.com/view.php?pic=30j0mcy&s=4

It is being developed using ActionScript 3 and Flash.

What algorithms and methods would you think would be best for this type of game?

The enemies run slightly faster than the player, so you can not out-run them, and they shouldnt be able to notice you behind obstacles and walls, unless they have already detected you, then they will follow until either of you are dead.

Of the suggestions made so far, based on your image, I think the simplest to implement might be the 'move to the last location at which the player was visible' method.

This should work quite well, although a limitation of the method is that if the agent reaches that point and the player is not visible, the agent will give up. Obviously this probably isn't what a reasonably intelligent agent would do - using your image as an example, the agent would most likely head down the hall, since there's really nowhere else the player could have gone. The 'bread crumbs' method suggested previously might be preferable for this reason.

A problem with the 'bread crumbs' method is that if the agent reaches a junction, it will always know which direction the player went (assuming the 'trail' is still fresh). You could certainly rationalize this though by saying that the monster can 'smell' the player if the player is close by. You could also factor in sound by sending the monster 'sound cues' when the player is moving.

Really, there's no one right answer or 'best' method to use. What method to use depends on a number of factors, such as how sophisticated you want the behavior to be, how comfortable you are with AI algorithms in general, how much time you want to spend on the implementation, how much processor time you can make available for the AI, how exactly the world is represented internally, etc., etc.

I am not too familiary with AI and pathfinding algorithms. I've used Astar for a few games and laborations though.

I've also tried a waypoint system where the enemy goes to the waypoint that is closest to the player _and_ closest to itself, if the player is out of line of sight when the enemy reaches "last location seen". It worked ok, but then there were problems with walking through walls so I had to add a LoS feature so that the enemy never moves to a waypoint that is out of line of sight (there was a lot of waypoints in the game, and always one in every corner).