Hi. First off, sorry if I'm asking in the wrong place, or a common question, or a completely stupid question.

I'm doing a simple roguelike. I plan on doing an AI system through a need-based system; hate, fear, love, necessities, etc. However, if the monster can't find what it wants in it's FOV, then it should go wandering.
I know I can do pathfinding through A*. However, this would find the shortest path from A->B. My original idea was that: (in some, weird kind of pseudocode)

if(cannot see anything interesting){endpoint = random(point on map);pathfind_to(endpoint);}else{interact(in some way);}

But the way my dungeon generates (pretty badly, with a lot of straight corridors and stuff), this would almost certainly lead to monsters going backwards and forwards across the same corridors.

I had an idea that the monster should wander semi-aimlessly to that point, but not straight to it.
First off, is this just a stupid idea? Would it give a signifcant difference to just doing shortest path to a random point, rinse and repeat?

Is there any algorithm that creates a path from A->B, but not the shortest route?

Thank you for your time, especially if I've been talking BS. :P

-Mark.

EDIT: I'm starting to doubt this existing, or it being effective if it does. Googling it returns this post as top result. :P

You could store the tiles or areas where the monster has explored, and then if there's nothing interesting around, go towards the nearest unexplored area.

This way the monster isn't aimless per se, but just appears to be searching or exploring.

I can see what you mean, and it sounds good.

I'm not entirely sure by how you mean 'nearest unexplored area'. Well, I can imagine it, but not put it into words, text, or code. If we say this:

0000000000000000000111222222000001M12222220000011122222200000000000000

(Hopefully that displays alright).
With M being the monster, 1 being what it can see, 2 being where it has been. So trying to show the monster has walked straight from the right edge.

Obviously I can see that going anywhere U|UL|L|DL|D would be not explored, but how could I specify this?

Only idea I can think of is check the field of view from every potential square it can move to (that hasn't previously been explored?) and see which has the highest percent of unexplored squares.

Thanks for the quick reply.

-Mark.

Well I think that sounds like a good start. Are there any behavioral downsides to it, or are you concerned with efficiency?

Anyway, I like that you're not going for the standard-ish walk-around-in-rings AI that so many RPGs feature.

I don't think efficiency matters too much. If there becomes a serious speed issue anywhere, I'm pretty sure I could change the input system to allow me to use spare time for calculating things.

Issue I can think of in that form would be a *standard* monster has a viewing radius of 3 or 4 tiles. I'm sure it could quite easily get stuck and start wandering back and forth as each tile gives the same exploration proportion.

The other point would be dead-end rooms...no way out, except by random chance.

I'm sure there would be some way around it, but (as you can probably tell) I'm extremely new to forms of AI.

Is that what you meant by 'behavioural downsides'?

Sorry for being slow on the uptake. Happens all too much.

-Mark.

I'm no AI expert myself, but maybe you could use Dijkstra's algorithm to find the nearest unexplored tile (or tiles).

I recommend that you read up on backtracking and also on graphs and graph traversal algorithms (DFS, BFS).

Regarding backtracking, there's a set of video lectures from Stanford available here where among other things, they give an excellent explanation of backtracking with lots of examples (It starts on lecture 10). You'll need to understand it to understand the above graph algorithms.

Actually there are also a few lectures on graphs (among the last few lectures).

Gage64: They seem to be good lectures. I might check up some other ones. :P

In regards to the backtracking, I'm afraid I don't see exactly what you mean, and how it relates. Most of the things posted seem to be along the lines of permuations; strings, or sums of numbers.

I can (roughly) understand the DFS/BFS. But how do you get to the search tree structure in the first place?

If I have my map: would I make a graph with each floor tile being a node?

I'm sorry if I'm completely failing to grasp the point.


Thank you very much for the replies. :D

-Mark.

Quote: Original post by Ahnfelt
I'm no AI expert myself, but maybe you could use Dijkstra's algorithm to find the nearest unexplored tile (or tiles).

That's more or less what we use in Widelands to implement a scout, and it works pretty well (modulo bugs unrelated to that idea).

Keep in mind that at some point, the monster might have explored everything though; in that case, you could either reset all fields so that they are considered to be "unvisited" by that monster, or you keep track of when a field was last visited, and go to the field which has not been visited for the longest time.

The latter would result in some kind of patrolling behavior in the long run, though you can still randomize it.

Edit to add: I don't think the backtracking ideas apply here. This would only be interesting if your goal were to have the monsters "consciously" explore the whole map. From a rogue-like, I wouldn't expect that, so I would go with Ahnfelt's suggestion. As far as your search graph would have a node for each tile, you have the right idea there.

">Here's another lecture. It explains DFS and uses maze traversal as an example. Hopefully it will answer some of your questions.

And yes, each tile in the map can correspond to a node in the graph. The lectures I linked earlier have more information on graph representation.

The Stanford lectures talk about the general structure of a backtracker. If you watch some of them and then the lecture above on DFS, you will hopefully see how DFS is a fairly straightforward implementation of backtracking (but make sure to look at the examples from the Stanford lectures as well).