Re: Precise Permissive Field of View: Request for comments

On Apr 24, 11:32 am, Jakub Debski <debski.ja...@xxxxx> wrote:
I have no time right now to play with it more. Did you try how many FOV
calculations can be done per second with different radius?
If it is fast enough (>500 calculations per second then I will probably
use it)

Here is a table of results. Cave random uses the 'cave' map which I
distributed with the los-demo. This is just a randomly generated map I
filched from another LOS demo because it had lots of interesting
situations. It is random in that each FoV calculation chooses a random
x and y location. Only those locations in the open were used for FoV.
That is why there are only 8141 trials. It was mostly an open map
(~81% open :)).

Note that 'optimized' is nothing special. It is merely the difference
between no optimization flags ('Debug mode'), and standard
optimization flags ('Release mode'). Optimization flags seem to make
an order of magnitude (!) difference between the results.

Note that these were run using a Intel Core 2 Duo (2.00 Ghz) CPU. Only
one of the cores was used (based on %CPU usage of the process). This
would tend to bias my results to be too high.

Cave random:
radius 80: Delta time for 8141 trials: 25516 = 319.05
radius 30: Delta time for 8141 trials: 21360 = 381.13
radius 10: Delta time for 8141 trials: 8266 = 984.88

Cave random (optimized):
radius 80: Delta time for 8141 trials: 1765 = 4612.46
radius 30: Delta time for 8141 trials: 1547 = 5262.44
radius 10: Delta time for 8141 trials: 656 = 12410.06

Mutual starting used your demo map for mutual-visibility with the
starting (fairly restricted) view.

Mutual starting:
radius 80: Delta time for 10000 trials: 6813 = 1467.8
radius 30: Delta time for 10000 trials: 6812 = 1468.0
radius 10: Delta time for 10000 trials: 6656 = 1502.4

Mutual starting (optimized):
radius 80: Delta time for 10000 trials: 687 = 14556.0
radius 30: Delta time for 10000 trials: 687 = 14556.0
radius 10: Delta time for 10000 trials: 671 = 14903.1

This is the closest thing to a worst case that I can think of. 80x25
room that is completely open.

Completely open:
radius 80: Delta time for 10000 trials: 68422 = 146.15
radius 30: Delta time for 10000 trials: 45813 = 218.28
radius 10: Delta time for 10000 trials: 10484 = 953.83

Completely open (optimized):
radius 80: Delta time for 10000 trials: 4531 = 2207.02
radius 30: Delta time for 10000 trials: 2703 = 3699.59
radius 10: Delta time for 10000 trials: 453 = 22075.05

Notice that even in this crude graph, there is an elbow. The
difference between radius 30 and radius 10 seems to be higher in most
cases than that between 80 and 30. I believe that this is due to
caching effects, and the limited width of each board (80). Also, the
completely open worst case seems to do slightly better in some cases
than the random cave. I think this may also be due to caching effects
since LoS is being done repeatedly from the same source in the
'completely open' example.

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.

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

nice.
Some time ago I started to work on RoguelikeLib http://sourceforge.net/projects/roguelikelib/
I think your FOV algorithm could be one of the algorithms to use there.

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.

At home I have a newer version with improved interfaces and some other
things implemented. I will put the new version and will make CVS
repository maybe today.

I've looked at your old source, and it is interesting. I haven't seen
anything appear on the CVS yet.

I would like to create a generic library, however it's hard to make a
good interface usable for every project, because of different data
representation. For example in case of pathfinding map data can be
binary (blocks or not) or variable (cost of movement).

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. 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. :)

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. And there should be a default map data
structure that implements a fairly straightforward way of handling all
of these requests.

The purpose of this library is to fulfill requirements of all
roguelikes:
< snipped list >

I think that having an ultimate list is good. But you should start
small. Create one of those algorithms that works well. 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. It would be difficult, but really handy to
have an excellent implementation of a few of them.

The problem is also to choose the proper way for passing parameters.
Most of the map generators should have options for
- diagonal movement
- doors at the end of corridors
- "transitive closure" guarantee
- min. number of rooms
- max. number of rooms
- percent of empty cells needed on map etc.

This could be passed as a pointer to structure or as long list of
parameters... Or setting the parameters for the whole library,
because the algorithms could depend on the game...

I would shy away from parameters for the whole library (except for
possibly something to set which parts of the library are to be used).
Instead, I would do this on a module-by-module basis. I would probably
create a settings class that had some set of reasonable defaults and
used the '<<' chaining operator to make changes. Then I would pass a
reference to that object to the algorithm concerned. The parameters of
the different algorithms should be indepent as much as possible. But
it might be useful to have some parameters that could be passed to
multiple algorithms. A diagonal-movement parameter would be important
both for map-creation and pathfinding, for example.

C sucks ;)

I prefer programming in C++ to programming in C. However, C bindings
are useful to any library. The reason is that many languages (python,
java, etc.) have ways of natively interfacing with C. So if a library
has C bindings, then it is easier down the road to make your C++
library a C++/java/python/C library and reach a wider audience. This
is my main concern.

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.

-D

.

Relevant Pages

  • Re: Compressing your levels
    ... But there are countless algorithms that work ... that it all depends on how you calculate the "energy" of map squares. ... meaningful values of "better") for a particular game remains open. ...
    (rec.games.roguelike.development)
  • Re: Precise Permissive Field of View: Request for comments
    ... performance tests and a more precise complexity analysis. ... I think your FOV algorithm could be one of the algorithms to use there. ... For example in case of pathfinding map data can be binary or variable. ...
    (rec.games.roguelike.development)
  • Re: [site name removed] World of warcraft wow PowerLeveling Power Leveling online game
    ... You can treat any discrete map as a graph; this may be the best option if there will be multiple geometries involved. ... The system they used has a set of "nodes" that make up the whole game map. ... These are linked together by mathematical transformations called "doors" that say how one node's coordinate system relates to another's. ... It would probably be best to make coordinates and vectors be opaque datatypes, so that algorithms working with them don't get horribly complicated and buggy. ...
    (rec.games.roguelike.development)
  • A map geometry system
    ... I have been experimenting with a new type of map structure: ... It consist of a set of rectangular pieces and some ... Line-of-site and related algorithms will have to be done by a flooding ... finding a "straight" route from one point to another is not ...
    (rec.games.roguelike.development)
  • Re: Collection vs well defined transfer objects
    ... > object in the Map or two different Integer objects in the Map. ... else beside the interface signature in any case. ... > handler would simple get the result from the Business Object and place ... > are a custom data type or a basic data type, ...
    (comp.object)