Subject: Slow algorithm (was: Re: Searching empty places within a larger region)
Date: Wed, 13 Mar 2002 09:25:46 +0100
From: Hansjörg Malthaner <hansjoerg.malthaner@danet.de>
Newsgroups: rec.games.roguelike.development

Hi,

I think I found an algorithm that can solve the problem, but it's sloooow:

1) determine all empty IxJ squres in the XxY region, regardless if they
overlap or not -> put them in a list.

2) Take a random entry from the list

3) Remove all entries from the list, that intersect withthe chosen entry

4) goto 2 until N entreis have been picked

That should work (not implemented yet) but steps (1) and (3) are slow ...

c.u.
Hajo