### Merrak's Isometric Adventures -- In-Game Map Editor

#### merrak

• Posts: 1788
Wow, your demos are awesome! Reminded me of some puzzles I saw in point and click adventures. It is a higher math to me though...

Thanks! I make a lot of little demos, mainly so I can debug these routines... also hoping that a few people play with them and maybe catch something I didn't.

Cool demo! But the clipping doesn't seem to work for some concave polygons...

Speaking of which, whoops. Actually, I shouldn't have said "general polygons", because concave is a special case. Sutherland-Hodgman may produce extra lines and multiple polygons if you have a concave polygon.

The rest of my code that processes the result assumes only a single polygon with no extraneous lines is produced, so anything else will break it.

There are plenty of other algorithms out there, but Sutherland-Hodgman seemed to have a good balance of simplicity, efficiency, and generality, and also handles all the cases I'm imagining I'll throw at it. I looked at Greiner-Hormann clipping algorithm, too.

#### merrak

• Posts: 1788
Success! Sutherland-Hodgman did the trick. I was finally able to render a shadow. This is what the render was supposed to look like:

Figure 1. It's been a long week.

There's still quite a bit of work left to do. Obviously the shadow shouldn't be drawn over the base of the pillar. I had a plan in mind for that, but I think I might discard it in favor of using Sutherland-Hodgman again. I already have it implemented and verified it works. I'll need to write another procedure to ensure all wall faces are convex polygons. Worst case scenario is I'll just define the wall faces manually or write a separate program to deal with that. But I'd like to have that built into the loading process.

So that's a job for tomorrow. In the meantime, I made a photo-montage of the debugging process. Image #1 was pretty bad  After that, though, you can see the intended shadow appear. Most of the work was in keeping other polygons out of the image.

Figure 2. 3D isn't easy.

Image #6 along with the entire bottom row of renders was made after implementing Sutherland-Hodgman, but the first two before fixing another little issue. The pillar is made up of "wall planes", and sometimes only two of the four vertices would actually project to the floor. Imagine a line drawn from the light source, through the vertex, and to the floor. But if the light is below the vertex, it wouldn't hit the floor--it'd hit the ceiling. The result is that the light vector would have to point in the opposite direction to intersect the floor, meaning the shadow would render backward.

In image #7, the floor was casting a shadow on itself... whoops!

« Last Edit: June 21, 2017, 11:33:30 pm by merrak »

#### Bombini

• Posts: 898
Congratulations!

#### merrak

• Posts: 1788
Thanks! Next I need to figure out how to optimize all this code.

Edit. Drawing a few sketches over the renders helped me visualize what the next step will be. The current process that renders the shadow (which is incomplete) has 14 steps... seven for Stage I (on game bootup) and seven for Stage II (on shadow draw). Ideally, stage II would be called in the drawing loop, which would allow me to update shadows every frame. Alternatively, I can call it when the scene is loaded.

There's a bit of an optimization problem in the wall faces. The time for Stage II to run is a function of the product of the number of wall faces (continuous walls), wall planes (physical parts of the walls), and light sources... so 3rd order polynomial time. That's bad for something I want executed every frame, so keeping the number of wall planes to a minimum is ideal.

On the other hand, if I have a lot of wall planes, I may not need to update every single one... such as if the player was carrying a weak lantern.

Stage I is a complete mess right now. For one thing, almost every little step prints output to the log. So I need to clean that up. I have redundant classes that can be organized better (wall plane, tile plane, wall face, tile face...  ) I also need to write a flexible procedure that partitions wall faces into neat little rectangles, so that I can play with the parameters and work out a good balance for the optimization problem.

So, ugh, quite a bit of work.  But at least I have a direction now, so that's a plus. This is the desired result:

Some of the wall faces overlap each other, which is a potential redundancy. In practice, this kind of room would be labelled "bad level design" because the player character could walk behind the pillar and disappear from view. To allow this kind of structure, I would split this room into two sectors, like demonstrated in the last video I posted. That also means the "special note" in my plan (above) is a non-issue... which is good news because it was the problem I was least looking forward to solving.

« Last Edit: June 22, 2017, 03:17:09 pm by merrak »

#### Majora64

• Posts: 498
I was watching a game developers conference on Diablo and he briefly went over issues with differentiating walls and tiles and actor location...dunno if it'll help but I figure it might be worth a shot to check it out or maybe it'll give you some insight.
https://www.youtube.com/watch?v=VscdPA6sUkc

He talks about Floors/Tiles around the 20 minute mark...said something about how he was trying to make walls and tiles work together but he should have just worked around the tiles...idk, I'm sure youll understand it more than me.

« Last Edit: June 22, 2017, 03:43:02 pm by Majora64 »

#### merrak

• Posts: 1788
It sounds like he's describing the same problem I ran into on a couple of occasions. I couldn't tell if it was for the same reason, though. For my code, every actor is represented by a single point (x,y,z), but the walls and actors graphics span multiple points.

Two year-old screenshot!

If the actor gets too close to the wall, a clipping error occurs. I got around this by playing with different sizes of collision radii. Eventually I found one that was just large enough to prevent the problem, but it was still bigger than I would've liked (about one tile length in diameter).

#### merrak

• Posts: 1788
Demo 4. My "growing squares" algorithm came together rather nicely. I probably didn't use the most efficient method, but it runs at a stage where speed isn't essential--so I went for a simpler idea that's easier to visualize. "Growing squares" is a bit of a misnomer, since it produces rectangles... but that's the name I assigned in my notebook so it stuck.

The goal is to take any polygon region, with or without a hole, and with 90-degree angles, and partition it into rectangles. I haven't thought about whether or not it finds the optimal solution, but I would be surprised. I went with the first idea that came to mind. On the small scale I'm using this on, if I have lag due to too many wall face partitions, finding the optimal solution to this problem is unlikely to fix it. So, here's my result.

<a href="http://static.stencyl.com/games/37076-0.swf" target="_blank" class="new_win">http://static.stencyl.com/games/37076-0.swf</a>

It's kinda hard to read the text, but here's what it says. Click on tiles to toggle them (create and remove holes). Once you're satisfied with the terrain, press enter to generate the partitions. Press r to start over. This is only a quick test, so if you need more than 14 colors, some partitions will share the same color. Sadly, this demo took me more time to debug than the actual algorithm--but it's much easier to progress knowing this works, so it's worth it.

I realized there's another good use for this algorithm. Suppose you are using the Tile API to generate a bunch of tiles, but now you have hundreds of individual collision boxes. You can use this algorithm to compute and construct a small number of rectangle terrains to replace the tiles' individual collision boxes.

I built this on top of my own version of the AI Tools extension (because I use a graph), so I could wrap this into a future release. But the algorithm itself is a simple idea that could be implemented using the Tile API instead. Here's how it works if you want to use it for yourself or improve it.

Consider a 2D array of uncolored tiles and the goal of coloring them in such a way that tiles that make up a larger rectangle are colored similarly. Pick the next available color and color the first uncolored 1x1 tile (searching from upper left to bottom right).

If it is possible, add a new column and a new row to the current partition. To add a new column, every tile to the right of the current partition must exist (not a hole) and be uncolored. Keep adding new columns and rows until it is impossible to add either. Then start over with a new color and the first available uncolored tile.

Progression might look like this (where X is a hole):

Code: [Select]
`"Growing Squares"Input: a 2D array of uncolored tilesOutput: a 2D array of colored tiles, where colors represent rectangle partitions0. Set next_color to 11. Starting from the upper left and searching rightward and downward,   pick the first uncolored tile at (r,c). If there are no uncolored tiles, then done.2. Set the color at (r,c) to next_color3. Set width to 1 and height to 14. If every tile to the right of the (width x height) box exists and is uncolored, then increment   width by 1. Color all the tiles in the new column.5. If every tile to south of the (width x height) box exists and is uncolored, then increment   height by 1. Color all the new tiles in the new row.6. Repeat steps 4 and 5 until neither width nor height can be incremented.7. Increment next_color by 1`

#### merrak

• Posts: 1788
I got a pretty good chunk of the plan I outlined last week completed and verified in working order. One issue I didn't expect (but probably should have) is that I had the vocabulary mixed up in a couple places. That didn't affect the demo, but it sure made reading the code difficult.

It's tedious, but I think taking the time to rename the classes will be worthwhile. There are a lot of little pieces that fit together. The top level is straightforward: Maps are broken into sectors, and sectors into individual tiles.

To render in 3D, I need to break complicated structures into simple components--so the motivation is simple geometry. Tiles are made up of planes ("wallplane"), and when tiles line up to make a wall, I'll call it a "wall group".

I'll refer to this old image, which colors what are now referred to as "wall groups".

The next task, which I just finished, is to break wallgroups into walls. I think a good analogy would be to imagine how a larger wall is constructed from pieces of drywall. "Walls" refer to the individual pieces of drywall that are grouped together to create a single seamless surface (SSS). I want the walls to be rectangles (in grid coordinates--so skewed in screen coordinates). This is very important because I can create a coordinate system so that the left and top edge of the wall are coordinate vectors. This speeds up the math.

In the original successful test, I didn't have a concept of a wall. The shadow was cast against each wallplane (of which each pillar had 4 and each floor tile had 1). That's a lot of projections. By grouping wallplanes into rectangle walls, I'll have far fewer projections.

Here are some of the walls, created by dividing the wallgroups using the "growing squares" algorithm:

Figure 2. The demo still has the old vocabulary, which doesn't help the vocabulary situation.

There are 17 total in that image, but that's down from hundreds. You can see the floor has been divided up so that it's represented by four rectangles instead of one polygon with a hole in the middle.

I also had a class called a "tileplane", which was supposed to be a bitmap related class. I ended up using it for calculations, which is the point where the code became very messy. Part of my cleanup effort will be in taking out that redundant role. All I really need to do is mark some wallplanes as visible, which is easy to do since each one has a normal vector that will let me determine if it is facing the viewer or not. A "tileplane" will now just be image data that is attached to visible wallplanes.

The final complication is, like last time, the stairs. But, just like with pieces of physical drywall, I can cut out parts to make it fit non-rectangular spots. The important thing will be to do the cut after all the calculations. Once the calculations have been performed, I can either clip or mask out pieces of a wall that are covered. Each wallplane will save the clip data. I'll recycle the name "wallface" to represent the unobstructed, visible polygon that is a subset of the wall.

The last benefit to all these efforts is that I'll finally be able to represent my windows and doors in the maps. This is an old screenshot, but it illustrates the problem with doors and windows:

Imagine each tile fitting in a box. The visible part of the door is set back about a third of the way into the box. The visible part of a window is set back about 2/3 of the way into the box. And, of course, the stairs don't line up with any coordinate plane at all. These scenarios weren't handled at all with my original strictly tile-based solution. That was okay when lighting was set per tile, but the map's geometrical representation now needs to be generalized.

#### merrak

• Posts: 1788
Shaders Solution. One important thing I've learned to appreciate more is note-keeping. Document, document, document! It's easy to write off documenting as a "one-level-removed" activity, but managing large programming projects is much easier if it's clear how every piece works together.

I made a nice little flow-chart showing the rendering process, albeit only for tiles.

The shader part is where I am at now. The real shader may have to wait for the next release of Stencyl, since I'll need some upcoming features to implement it. But if I'm careful, I can implement a lot of it in software.

Part of pulling this off will be a good solution to the optimization problem I mentioned earlier. I can re-draw the entire scene every frame and achieve about 40 FPS. But about a third of the scene doesn't need to be drawn at all, because a scene full of tiles forms a diamond and the corners are always blank. By only re-drawing wall faces that are updated, I can (hopefully) achieve 60 FPS. That's not great for a game with only 384x320 resolution, but I'm basically writing a "rough" ray-tracer.

This means rooms for which the player carries a lantern will need to have few updating wallfaces--so long, deep corridors. Fortunately, that was the kind of structure I was thinking anyway--so nothing lost with that restriction.

Just for fun, I made a promotional poster for Temple of Idosra. I liked the poster that the developers of House made, so I drew up one of my own.

I like how it came out, although I think the tagline is too cheesy. If I think of a better one, I'll revise the poster.

#### Bombini

• Posts: 898
I totally agree. Documentation is so important. I need those flow charts for some areas as well otherwise i just keep forgetting how it works.  I dont think that the tagline is cheesy actually. Taglines need some punch

Cheers!

#### merrak

• Posts: 1788
I realized it looks a lot like a flyer for a local band concert. Maybe I should print off a few and post them on local bulletin boards when the game is closer to release. If anyone is in Durham, Raleigh, Chapel Hill, Wilmington, or Eastern NC and sees one, you'll have to let me know

#### squeeb

• Posts: 1223
If you want,  I'll post some up here in the Pacific northwest as well

#### merrak

• Posts: 1788
That's be awesome   My wife is from Spokane, so I visit there every so often.

#### Bombini

• Posts: 898
I can print some for Berlin/Germany if you want

#### Majora64

• Posts: 498
Live in Portland...would love to post some and frame one for myself I like the poster and the movie like text but I think the title font and "what secrets do the shadows hold" needs some tweaking. The goosebumps font of "Idosra" isn't in my personal taste especially if this is more dungeon-esque...I'd expect something more like Tower of Druaga, LOZ, Dark Souls...etc. Would also love to see some color somewhere too... I know on some of the horror posters like Exorcist or Insidious, one word in the text is colored red and everything else is black and white which I think is a very nice touch (however idk what direction your game is going so take this with a grain of salt). Just my 2 cents lol. I'm so excited to see all ur work put into a full fledged project!