Sign in to follow this  
PurpleSky

Exploring a map - dijkstra?

Recommended Posts

PurpleSky    122
hi, im a newbie in game programming (just taking it at uni this year) so please bear with me... im working on a game where the player initially has no idea about the map. so the player has to explore the map and find stuff (Player has limited vision). There are several types of obstacles that he has to get past. Is there a specific kind of algorithm that is suited to 'exploring'? Im currently thinking of dijkstra, but im not sure...Pls advice! Thnx!

Share this post


Link to post
Share on other sites
DrEvil    1148
If the player, as in human player is exploring the map, what do you need dijkstra for? I'll assume you mean to get AI to explore the map? dijkstra would be fine for that.

Share this post


Link to post
Share on other sites
PurpleSky    122
Thanks Yes im talking abt da AI player. i dont need a shortest path, and i dont have a specific goal. at this level, i just want da AI player to explore the map as much as he can in limited time.

Share this post


Link to post
Share on other sites
Colin Jeanne    1114
If you have nowhere in particular that you're trying to get to then breadth first search or depth first search should be fine. If you're trying to get somewhere then you might want to look at A*.

Share this post


Link to post
Share on other sites
daniel_i_l    295
If your searching the map for a certain type of object, and you don't know where the closest object of that type is on the map - use Dijkstra and terminate it when an object of the correct type is found.

Share this post


Link to post
Share on other sites
ToohrVyk    1596
A possibility is to set individual units to "explore" tasks. Then, the unit would examine adjacent tiles and determine which movement would reveal the highest amount of terrain (that is, it would move directly into uncharted territory). If no adjacent tile would reveal terrain, I would suggest finding the nearest unrevealed tile and moving straight to that tile. An additional constraint that would be useful is to only consider accessible unrevealed tiles only (both when examining adjacent tile revealing power and new destinations), so units don't spend time exploring areas that cannot be reached yet, and neither do they try to get to them.

Now, if you have several units exploring at the same time, you don't want them to overlap each other. This would happen naturally if the units are close to each other (the first's exploration would cause the second one to take a new direction), but units in their "move towards new exploration start point" would probably annoy each other (since the closest unexplored point might become explored during transit). I would cause an exploring unit's movement to be interrupted if another unit explores its destination tile, thus prompting the stopped unit to compute a new path, possibly to a new area.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this