fov_permissive2 - Bumps usage

[wgebczyk]

Hi,

I'm looking through impl for permissive FOV and I cannot find usage of bumps passed to check_quadrant.
Of course there is mem shenanigans, adding to this "collection", but is there code that is using that collections content in a way that it affects visibility?

libtcod/src/libtcod/fov_permissive2.c

Line 294 in 713817b

check_quadrant(map, pov_x, pov_y, 1, 1, max_x, max_y, light_walls, offset, limit, views, &bumps);

[HexDecimal]

check_quadrant passes bumps to visit_coords which then passes it to several other functions.

Note that the memory allocated for ViewBumpContainer is pointed to by the non-owning ViewBump* attributes in View structs. This is how check_view is using the ViewBumpContainer even though it's not directly referencing it in its parameters.

Functions like add_shallow_bump assigns bumps to views, which are then tested by check_view, I think. I actually never got familiar with this algorithm, so I can only talk about what I see when I read the code.

[wgebczyk]

ViewBumpContainer is used in following places:

• TCOD_map_compute_fov_permissive2allocation of memory to its data member
• check_quadrant resets count to "clear" container
• data member is used in add_shallow_bump and add_steep_bump only IMO to inc count and set new structure values. New entry is used obviously, but pointer to this structure is passed and newly created structure is used via this pointer not whole container.

The collection is not iterated or randomly accessed by any add_*_bump. The collection is preinitialized with potentially maximum number of bumps which is all possible tile/cell.

From that it seems that ViewBumpContainer serves as kind of local memory allocator only. On other hand when allocated mem for Bump structure is accessed via ViewBump* pointers created in add_*_bump methods, then structure could be locally allocated (probably even on stack) and pass to child calls.

I'm not saying if current code needs to be changed. I'm trying to understand significance of bumps-collection.

EDIT: The views and bumps are separate memory regions right?

  View* views = malloc(sizeof(*views) * map->width * map->height);
  ViewBumpContainer bumps = {0, malloc(sizeof(*bumps.data) * map->width * map->height)};

[HexDecimal]

I think you might be correct. How bumps is being used is simple enough that it could be replaced with a stb_ds array like active_views was.

Do you think that views don't need to have ViewBump* pointers and can maybe hold that data directly? Or could ViewBump* be changed to const ViewBump* or something?

Previously a lot used to be static variables randomly accessed by the functions in this module until I made the implementation reentrant. My refactors may have changed how easy or hard it is to read the code, and my inexperience with the implementation might have left something that'd be easy to refactor that I missed.

The views and bumps are separate memory regions right?

Yes, and that should maybe be clear from the separate mallocs. I was too paranoid to allocate them as one block when refactoring. View has pointers to the memory at *bumps.data, but I think that was clear, or at least that's what I keep seeing.

There's also active_views which technically has it's own allocation. That variable could be moved up a function if we wanted to reduce allocations, but that isn't a priority for me.

[wgebczyk]

In fact I'm looking at c# port of this algorithm, where I've found this collection not needed there. I've checked other impls and found this one. I'm not and c/C++ expert, but I will look at it locally what would happen if this custom allocator will be removed. In a day or two will report back :)

[HexDecimal]

This is a C99 version, and I don't have benchmarking setup for it so unless it makes the code easier to read I wouldn't worry about changing it.

A link to the C# implementation you looked at might be useful for later reference.

[wgebczyk]

I've started with this code: http://www.adammil.net/blog/v125_roguelike_vision_algorithms.html
From it I've found out that collection only gather elements.

And then I will drop my check with libtcode :)

Thank you!

[HexDecimal]

Turns out I already have a link to that page included in issue #71, that issue tracks FOV resources and the changes I wanted to make to FOV in libtcod but didn't have time for.