Author Topic: Recursive portalcasting.  (Read 14577 times)

Kevin Granade

  • Rogueliker
  • ***
  • Posts: 83
  • Karma: +0/-0
    • View Profile
Recursive portalcasting.
« on: July 04, 2014, 02:35:47 AM »
This is something I've been meaning to post about for a while, but I kept forgetting to do it.  The recent threads on FoV reminded me.

I made an adjustment to DDAs shadowcasting implementation a while back that people may find interesting.
Consider the action a shadowcaster takes on a single square, it is either blocked, meaning the shadowcaster simply proceeds to the next square, or it is open, and the shadowcaster processes it recursively.  I added a third option, which is processing the square recursively as per open squares, but setting a "portal" flag when doing so.  When the flag is active, the algorithm marks visibility as usual, but also sets the state of the square differently.

When later rendering the scene, this state is checked, and the scene from the other side of the portal is drawn in this "portal shadow".

There are several more features I need to add to integrate it with the game, but I doubt anything will be as challenging as the portalcasting implementation.
WIP code: https://github.com/CleverRaven/Cataclysm-DDA/pull/6951
Example images:
Standing on a road near two portals leading to a swamp.

Standing in the middle of a mall with a nearby portal to an outside area.

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #1 on: July 04, 2014, 03:04:12 AM »
Sorry, I don't know the game. So by a portal, you mean something that you walk through and end up in some distant location? And the point is your portal shadows are showing you the piece of this distant place you see through the portal?

Neat idea, although I think it would be visually clearer if there were some kind of visual queue on the boundary of these shadows that you're seeing something through a portal, rather than relying on the player noticing the 0. Maybe some kind of greying effect or background on those tiles.

Kevin Granade

  • Rogueliker
  • ***
  • Posts: 83
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #2 on: July 04, 2014, 03:18:01 AM »
Sorry, I don't know the game. So by a portal, you mean something that you walk through and end up in some distant location? And the point is your portal shadows are showing you the piece of this distant place you see through the portal?
Yes, in the end I want the player and monsters to be able to walk, shoot, throw, see, hear, smell, i.e. everything through a portal.
Neat idea, although I think it would be visually clearer if there were some kind of visual queue on the boundary of these shadows that you're seeing something through a portal, rather than relying on the player noticing the 0. Maybe some kind of greying effect or background on those tiles.
I struggled with that a bit, though if you're walking around, having a huge swath of map swing around makes it pretty visible.  And if you're standing on a plain and the other side of the portal is a plain as well, who's to say that it would be all that noticeable?

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #3 on: July 04, 2014, 03:35:23 AM »
Neat idea, although I think it would be visually clearer if there were some kind of visual queue on the boundary of these shadows that you're seeing something through a portal, rather than relying on the player noticing the 0. Maybe some kind of greying effect or background on those tiles.
I struggled with that a bit, though if you're walking around, having a huge swath of map swing around makes it pretty visible.  And if you're standing on a plain and the other side of the portal is a plain as well, who's to say that it would be all that noticeable?

Yeah, I see what you mean on a turn to turn basis. Even with a plain-plain or desert-desert portal, I think you'd still see a seam. Idk, I'd highlight the boundary. It would be easy to implement, I think.

Kevin Granade

  • Rogueliker
  • ***
  • Posts: 83
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #4 on: July 04, 2014, 04:00:28 AM »
Actually it would be nightmarish to implement, ternary shadowcasting is already quite brain-warping.

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #5 on: July 04, 2014, 04:02:51 AM »
Well, surely you can tell when you've switched from showing one background to the other.

tuturto

  • Rogueliker
  • ***
  • Posts: 259
  • Karma: +0/-0
    • View Profile
    • pyherc
Re: Recursive portalcasting.
« Reply #6 on: July 04, 2014, 04:05:19 AM »
This is all kinds of crazy and cool. What would happen if you had a portal, which another end is next to another portal? Would you be able to view the third location through two portals? What about if the other end of the second portal would be behind of you, would you see yourself, staring into infinity?
Everyone you will ever meet knows something you don't.
 - Bill Nye

Omnivore

  • Rogueliker
  • ***
  • Posts: 154
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #7 on: July 04, 2014, 04:22:29 AM »
Actually it would be nightmarish to implement, ternary shadowcasting is already quite brain-warping.

Gah, hurts my brain to even think about it.  Nice job!

miki151

  • Rogueliker
  • ***
  • Posts: 264
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #8 on: July 04, 2014, 05:17:37 AM »
Neat :)  - I have portals in KeeperRL that you can shoot through, and thought it was pretty badass. I'm not going to copy your idea though :)
KeeperRL, Dungeon Keeper in roguelike style:
http://keeperrl.com

Kevin Granade

  • Rogueliker
  • ***
  • Posts: 83
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #9 on: July 04, 2014, 05:49:58 AM »
Well, surely you can tell when you've switched from showing one background to the other.
In what context? If you do it within the shadowcasting function, you now have another bit of state to track, and it's already a lot to handle.  If you do it in the render pass, it has to somehow find the edges.  In the code as it is each tile is rendered totally independently, the thing that is merged is various overlapping arrays of data like transparency, the various cell contents, lighting, etc.
What would happen if you had a portal, which another end is next to another portal? Would you be able to view the third location through two portals?
Not implemented currently, but you could write a reference to the map location the portal goes to to the portal array instead of a simple boolean, and recurse through portals.  It wouldn't be much harder.  The place where it becomes a pain is keeping track of all these different map locations.
Which reminds me, I forgot to outline how that works.
DDA stores map data in chunks we call "submaps", each submap has all the data associated with a 12x12 chunk of map.  There is a data structure that is essentially a 11x11 grid of these submaps that stays centered on the player at all times.  For the portal destination, we load a second map at the new location, and pull data from it when rendering the portal destination.  We'd need to load one of these for each portal in range, recursively.  This implies having all the monsters, fields, etc for each portal destination loaded (submaps are synced back to disk and deleted when the player leaves the area, and loaded on-demand when they enter an area).  also there is a certain amount of per-turn caching that has to happen, regenerting the transparency maps for each map and running dynamic lighting.  Luckily we only have to run FOV once for the visible area, the fact that we're using portals doesn't change that, each visible square is still only visited once, for a worst case of 121x121 squares visited.
This was also quite a pain to deal with when teleporting through a portal, I had to juggle the main map and the portal destination map around and get all their state set up right.
What about if the other end of the second portal would be behind of you, would you see yourself, staring into infinity?
This is a little tricky, it implies that multiple maps have the same submaps loaded, so there might be conflicts between them.  It's something I need to address for other reasons at some point, for now I'm deferring that and only loading portals at locations distant from the player.
« Last Edit: July 04, 2014, 05:51:46 AM by Kevin Granade »

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #10 on: July 04, 2014, 06:14:21 AM »
Well, surely you can tell when you've switched from showing one background to the other.
In what context? If you do it within the shadowcasting function, you now have another bit of state to track, and it's already a lot to handle.  If you do it in the render pass, it has to somehow find the edges.  In the code as it is each tile is rendered totally independently, the thing that is merged is various overlapping arrays of data like transparency, the various cell contents, lighting, etc.

Right, but you're doing some kind of row or column scanning, right? So you know what the first and last bit of shadow is in a row or column. That's the boundary. Maybe you're doing something much fancier than I thought?

Kevin Granade

  • Rogueliker
  • ***
  • Posts: 83
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #11 on: July 04, 2014, 06:19:12 AM »
Well, surely you can tell when you've switched from showing one background to the other.
In what context? If you do it within the shadowcasting function, you now have another bit of state to track, and it's already a lot to handle.  If you do it in the render pass, it has to somehow find the edges.  In the code as it is each tile is rendered totally independently, the thing that is merged is various overlapping arrays of data like transparency, the various cell contents, lighting, etc.

Right, but you're doing some kind of row or column scanning, right? So you know what the first and last bit of shadow is in a row or column. That's the boundary. Maybe you're doing something much fancier than I thought?
Technically it's scanning across rows/columns yes, but logically it's completely agnostic to iteration order, and I'd like to keep it that way.  Coupling at that level can easily interfere with caching in the future.

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Recursive portalcasting.
« Reply #12 on: July 04, 2014, 06:24:20 AM »
Alright, well, like I said, cool idea.