Re: fov algorithms comparison method

On Jan 20, 11:01 am, jice <jice.nos...@xxxxxxxxx> wrote:

For speed, I'm thinking about two different benchmarks :
- outdoor maps (20x20, 100x100 and 600x600 maps with random 1x1
obstacles)
- cave maps (20x20, 40x40, 80x80 maps with random BSP dungeons)

I think two more test could be used:

worst case scenario, empty field (20x20, 100x100, 600x600). It could
help illustrate (roughly) how much impact do obstacles have on time
used. It may be slooow, but there's no need to re-run it I guess :-)

- best case scenario, everything except player position is a wall
(20x20, 100x100, 600x600)


One extra question. Does your implementation of so-called diamond
raycasting show difference in speed between:
- player surrounded by a _ring_ of 8 obstacles, all other fields are
empty
- player surrounded by a field full of obstacles (all fields are
obstacles except player's position)

This is important. If there's a significant difference, it means
you're using unoptimised algorithm (or rather, unoptimised input
data).
I've run some tests on both mine implementation of 'diamond
raycasting' and Grim's, and when the field is full of obstacles the
operation takes nearly as much time as with totally empty field ! But
if there's only a ring of 8 walls around the player, the operation is
much faster (in case of Grim's Python implementation it's roughly 850
ms with all walls, 500 ms with a ring of walls on 600x600 field.
Benchmarked with unix tool 'time': 'time python fov_test')

In other words, the diamond raycasting algorithm's speed can depend
strongly on obstacles player can't see. I've already posted an
explanation in the other thread, but I think you didn't repply. To
make the diamond raycasting run better you'd need to feed it an
optimised obstacle map: without 'deep' walls which are surrounded by
walls from all 8 sides. The result would be the same and it would run
faster. This 'input data optimisation' would only need to take place
once per map generation and once per map change (wands of digging etc)

All your comment/suggestions are welcome. Do you think it's worth
adding such information on roguebasin ? Are the tests / criteria
pertinent ?

I'm eager to see the results. But 'elegance' should be described
verbally, I don't think you can assign a score to it. A 'flexibility'
score could be useful but I have no idea how to assign a score to it,
too.
.

Relevant Pages

  • Re: fov algorithms comparison method
    ... worst case scenario, empty field. ... strongly on obstacles player can't see. ... walls from all 8 sides. ... once per map generation and once per map change ...
    (rec.games.roguelike.development)
  • Re: Mechanical waves
    ... Play with the '2D ripple tank' and use your mouse to add a couple of ... walls and slots etc. ... simple too diffuse wrt the obstacles. ... the obstacle before the wave reverses. ...
    (sci.electronics.design)
  • Re: Intriguing new Line Of Sight algorithm (Java, Python)
    ... I think going one tile behind walls is what this algorithm needs to ... The original implementation assumes that all obstacles are visible, ... The obscure() method returns true for all walls, ...
    (rec.games.roguelike.development)
  • Re: The Berlin Interpretation
    ... I started doing something similar actually, whereby the player is ... but certain obstacles could send it back to the beginning. ... Replayability would be encouraged through an XBox style "Achievements" ... In the end though I ditched the immortality ...
    (rec.games.roguelike.development)