Random Walk + Exploration Algorithm for game AI. Scene Tiles

Question

I am trying to come up with an algorithm for random walking in a scene tile based game. The walker needs to be able to randomly navigate until all tiles are explored or until it finds the next level.

So far I have the tile as explored if the actor steps on it.

Then it finds the path to the center of the next tile.

But where its failing is it often thinks its finished exploring, or that there is no more tiles left.

Is there anywhere to look for some examples, as if I were to paste source it would be way long.

May be a good starting point for you: http://stackoverflow.com/questions/11165910/where-is-a-good-place-to-start-with-programing-a-random-path-on-a-grid and there's also a large collection of answers about pathfinding in general over on gamedev - http://gamedev.stackexchange.com/questions/1003/dynamic-pathing-algorithm-for-tower-defense-game. Possibly you can use A* but choose a random (unvisited) destination each "trip"? — dash, Oct 04 '12 at 20:09
You need to give some sample data a least. How are you storing your tiles? — Yatharth Agarwal, Oct 04 '12 at 20:10
I will look into flood fill. The problem would be if it reached a dead-end. It would remove the tiles it visited. Then the next nearest tile could be behind a long wall and corridor that it would fail to path to using A*. I would need to make a stack of every visited tile, then if next tile distance is > 1 tile. pop off tiles and backtrack? — Vans S, Oct 04 '12 at 20:28

score 1 · Answer 1 · edited Nov 14 '12 at 18:39

1

I made one like this on a Mac years ago, and solved it with "FLAGS" to determine if anything had already happened / conditions met...

If FlagFinal=1 then (exit) else ...

Most of the things in my game were done with flags.

So when meeting random strangers in the tile, it checked if other flags were 1. So... on MeetMilkMaid if FlagCow=0 then (do ask) else (do reward).

Hope this helps.

edited Nov 14 '12 at 18:39

Steve Czetty

6,147
9
39
48

answered Nov 14 '12 at 18:20

Stoned

11
1

score 0 · Answer 2 · edited May 23 '17 at 11:48

Hmm... if you mean truly random walking, then get a list of all the tiles, randomize it, then add the randomized items to a stack (or queue). Pop each tile off the stack as you walk to it.

Tile[] _tiles;
//... some code here to load the tiles

Tile[] _randomizedTiles;
//... some code here to randomize the tiles

Stack<Tile> _tilesToExplore = new Stack<Tile>( _randomizedTiles );

while ( _tilesToExplore.Count > 0 ){
    var l_nextTile = _tilesToExplore.Pop();
    //... some code to walk to the tile
}

If you mean pseudo-random "wandering around", then you could modify this approach by using a List<Tile>. Use your own custom solution for picking the next tile (rather than popping it from a stack) and simultaneously remove the Tile from the List. Keep looping as long as the List is not empty.

If you have a more advanced scenario (where you may not know the tiles beforehand, or where tiles may be inaccessible), then you may find this CodeProject article (and demo code) helpful:
A* algorithm implementation in C#

Further Info
Randomize a List in C#
Stack class (MSDN)

Random Walk + Exploration Algorithm for game AI. Scene Tiles

2 Answers2