Re: Precise Permissive Field of View: Request for comments

After serious thinking tyrecius13@xxxxxxxxx wrote :
It seems to perform about the same as or a little better than the
mutual visibility algorithm (given the biases of the difference in
processor). But it is hard to say how much the difference in
processors and other conditions affected things.

Thanks, that convinced me to use it as a default FOV algorithm in RoguelikeLib :)
New version is out http://sourceforge.net/projects/roguelikelib/
Also simple game that uses the library is provided.

Still as a packed ZIP, no CVS yet. I have strange problems with repository connection...

I am blown away at how much of a difference compiler optimization
makes.

Debug version usually is even slower due to a lot of additional checkings (range, memory allocation etc.)

That would be neat. And it occurs to me that shadowcasting could be
packaged up using a similar interface, so that a user of the library
could easily switch between them.

I really like your solution with the "context template".

A good interface for these algorithms has to be both composable, and
swappable. I think that a common theme with roguelikes is that
whenever somebody wants to do one, they have one or a few things that
they want to focus on that will be different and they would like to
not have to worry about the other stuff.

Right now I replaced all the code to stateless (no single class).
The interface is not yet very swapable, I will work on it with a new version.

This means that if somebody
is obsessed with FoV (like myself), I will want to swap in my own FoV
algorithm while using the default pathfinding capabilities (because I
don't really care about that). This will be different for different
people. So the library needs to be separated into different parts that
can interact with each other, and can interact with a user-swapped
version of each other seamlessly. This is hard. But it is the only way
to create a really cool rl library. :)

I agree. Probably with templates as you did it is possible.

As far as data representation is concerned, the library should
sidestep that as much as possible. Rather than relying on a particular
map data structure, it should have a map interface (not necessarily
using inheritance), that implements certain querying methods that
support various map algorithms.

I thought a lot about it. It would be great but is not really necessary.
Right now I use the defined simple map structure that algorithms work on. All the access to the class is defined by the interface.
Of course there are some speed issues, but in my opinion they are not important in case of roguelikes. To make a copy of a map (80x25) you just need to copy less than 2KB of memory. It's very fast.
Some algorithms need to transform the map to binary (0,1) or to values.
It requires again <2000 operations for the 80x25 map and it's again fast enough.

And there should be a default map data
structure that implements a fairly straightforward way of handling all
of these requests.

You are free to join this SourceForge projest if you want :)

< snipped list >
I think that having an ultimate list is good. But you should start
small.

I did :)
Basic functionality is already implemented.

Create one of those algorithms that works well.

Right now they work well enough. Next step will be to improve them.

Then after it
works on its own, add another and so on. I think that it would be
really easy to have a crappy implementation of everything on the list
that nobody wants to use.

To see what is necessary I wrote a very simple game that uses:
- Map management and generation
- Randomness
- FOV calculation
- Path finding

It's very simple and small (about 10KB) and could be a nice base for 7DRLs ;)

Good luck on your library. I would be happy to offer my advice,
integrate permissive-fov into such a library, or even write a couple
of modules for it if you wanted and I had the time.

I have integrated your code already (in a simple way). Check it out if you like to do some changes.

I'm also curious what would you propose for "game example". Do you like the structure of inheritance I did?
I don't want to use boost library with it's great "boost any" so I had to make a list of pointers to monsters. This is ugly, because there is no easy way to iterate through the list that can change (monsters can die). That's why I used also the second list of monster that died.

regards,
Jakub


.

Relevant Pages

  • Re: A dungeon generator
    ... rooms will not fit in the map, so your algorithm will fail. ... each level has 16 possible starting templates. ...
    (rec.games.roguelike.development)
  • Re: one sentence proof of 4 Color Mapping Problem; direct method
    ... for you to determine whether you can color this map with THREE ... So an algorithm for this machine would look ... building the algorithm in P to solve the NP-complete problems, ... Perhaps the equivalency is the idea that Eucl geom is what is ...
    (sci.math)
  • Re: A dungeon generator
    ... then it automatically turns in the former kind of algorithm. ... If it fails to generate a map ... rooms, then after a hundred more fails, five rooms, etc. ... each level has 16 possible starting templates. ...
    (rec.games.roguelike.development)
  • Re: fov algorithms comparison method
    ... The same set of random map must be used for each algorithm. ... FOV must be ...
    (rec.games.roguelike.development)
  • A Random Town Generation Algorithm
    ... I have implemented a random town generation algorithm algorithm. ... Pick a random point close to the centre of the map. ... And do the same for each of the new rectangles created by this until you've reached a minimum size. ... Ideally all these new created subdivisions should be stored in some list. ...
    (rec.games.roguelike.development)