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.
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."
Visit www.neobasic.net to see rubbish in all its finest.
Visit www.neobasic.net to see rubbish in all its finest.