06-29-2005, 08:29 PM

Create an algorithm that generates the shortest amount of "center points" from a random map. (for instance, 100x100?) The map is composed of passable (0) and unpassable (1) terrain.

Each center point "covers" all the points from which it can be linearly plotted. Each passable point on the map must be covered by a center point.

The random map should not be lame.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Let me put it another way. You're in a room and you want to find out how to place candles in it such that the light from each candle directly shines towards each wall, and you use a minimal amount of candles.

I estimate that the algorithm would require a density check: create a simple breadth first pathfinding search (A* without the numbers, really.) and then have it try to find a path from each point to each other point in the map. (that takes passable_terrain_tiles*(passable_terrain_tiles - 1) attempts) Count how many times each point was traversed. Maybe the density pattern will shed some light on this.

Each center point "covers" all the points from which it can be linearly plotted. Each passable point on the map must be covered by a center point.

The random map should not be lame.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Let me put it another way. You're in a room and you want to find out how to place candles in it such that the light from each candle directly shines towards each wall, and you use a minimal amount of candles.

I estimate that the algorithm would require a density check: create a simple breadth first pathfinding search (A* without the numbers, really.) and then have it try to find a path from each point to each other point in the map. (that takes passable_terrain_tiles*(passable_terrain_tiles - 1) attempts) Count how many times each point was traversed. Maybe the density pattern will shed some light on this.