impossible map algorithm challenge

[Agamemnus]

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.

[Agamemnus]

come on people,

don't you know why this is important?

Just reply :|

[Dr_Davenstein]

Sorry, might be fun... too busy though.

[Agamemnus]

:|

It would solve pathfinding forever..

[Agamemnus]

Extremely slow way to do it:

Go through all points.... one by one.... for each point go through all the points again, etc. Basically get all the possible center point combinations....... then order them and pick the one with the smallest amount....

This process is something like A^A^A/2 steps where A = xy.....