Stencyl 3.4.0 is now out. Get it now!

Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Messages - merrak

Pages: 1 2 3 ... 91
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="" target="_blank" class="new_win"></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 tiles
Output: a 2D array of colored tiles, where colors represent rectangle partitions

0. Set next_color to 1
1. 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_color
3. Set width to 1 and height to 1
4. 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

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

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

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  :P 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!

Ask a Question / Re: Get stuck on tiles after replacing them
« on: June 21, 2017, 08:13:27 am »
This is a Box2D issue. One workaround is that you can round the corners of the walking actors.

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

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.

I found another nail in the AABB coffin--overlapping quadrilaterals don't necessarily form quadrilaterals. Now I'm not sure if this would've been an actual problem due to specifics of the level geometry. I bumped into it just sketching out random shadows on paper.

But on the plus side, my research pulled up the Sutherland-Hodgman Algorithm. This solves the problem very nicely. Try it out below... draw two overlapping quadrilaterals (in clockwise order) and the intersection should be highlighted.

<a href="" target="_blank" class="new_win"></a>

The nice thing about this algorithm is that it works for general polygons--not just quadrilaterals. It's also runs in linear time; computational time is proportional to the number of edges in the clipped polygon.

My implementation is "baked into" the rest of my engine code, but if there's sufficient interest I'll make it a stand-alone extension.  The algorithm itself was simple enough to implement in Haxe--but setting up all the required classes for storing data and performing vector calculations took was a significant chore.

If you want to render 3D graphics efficiently, you'll need a good solution to the clipping problem. I liked the triangle flood-fill solution because it just piggy-backed so neatly on top of the code that loaded the levels, but it only works if all graphics are locked to a tile grid.

What does the rest of the log say? Were there more compilation errors?

Ask a Question / Re: Sorta a list by largest to smallest?
« on: June 18, 2017, 01:58:32 pm »
The "as number" block should ensure consistency across all platforms.

Ask a Question / Re: Sorta a list by largest to smallest?
« on: June 18, 2017, 12:55:56 pm »
Oh, put "as number" in the if statement. It should be

if (part of get item.....from list2) as number < (part of get item.....from list1) as number

Leaving out the "as number" means it is trying to compare text and won't be able to figure it out.

You beat me to it :) I was about  to say you get different behavior on different platforms with implied text->number conversions.

Ask a Question / Re: How to get the alpha value of an actor
« on: June 18, 2017, 12:50:10 pm »
Do you have an "Animation 0" for that actor?

Take 2. I reworked the math for detecting overlapping quadrilaterals and pretty much came to the conclusion that my "flood fill algorithm" isn't going to be useful.  :( I thought it was neat, too, but maybe I can find a use for it elsewhere. In order to get the speed I want, I have to assume every wall face is a rectangle.

On the plus side, the revised method won't require that tiles line up with the triangle grid, making it just a bit easier to have more elaborate rooms in the future. It's too late for this first generation of the isometric engine since I want to get back to Temple of Idosra. But for the second generation, I'm imagining a DOOM-style map editor instead of tile-based.

Performance will be a function of the number of visible wall faces, with drawing methods forming the most demanding stage. I'm thinking with hardware accelerated graphics, I could get a good number of wall faces.

So now two new problems need to be solved. First, I need(ed) to solve the point-in-polygon problem. This was actually pretty simple to solve using the crossing number algorithm. Basically, I draw a horizontal line through the quadrilateral and count the number of intersections. If it's even, the point lies outside the quadrilateral. If it's odd, then it lies inside. Demo:

<a href="" target="_blank" class="new_win"></a>

This can be implemented without raycasting using the line intersection algorithm I posted in April.

If you want to implement it yourself, here's what you can do

Code: [Select]
Input: V, list of vertices; (x1,y1) coordinate of a point to test
1. Compute (x2,y2) so that line segment (x1,y1),(x2,y2)  is guaranteed to span the maximum distance between any two vertices. (Note--I just used a horizontal line and set x2 to be the sum of all the x coordinates)
2. intersection_count := 0
3. for each vertex v_i in V
     3A. if line segment (x1,y1)-(x2,y2) intersects (v_i.x,v_i.y)-(v_(i+1).x,v_(i+1).y) then increment intersection_count by 1
4. return ( intersection_count mod 2 != 0 )

Notes: (1) this will work for any polygon--not just quadrilaterals.
       (2) This doesn't handle the case that (x1,y1) lies on one of the edges of the polygon itself. I handle this case elsewhere in my code.

The line intersection algorithm also returns the location of the intersection, which I'll need to clip the shadow quadrilateral so that it doesn't extend outside of the wall face. This part can be tricky, but the linear algebra won't be as complex as the AABB projection. So, things are looking up on this front.

Problem #2 is replacing the triangle-based floodfill algorithm with one that builds rectangle wall faces. While I'll have more wall faces this way, I can use faster methods taking advantage of them being rectangles. I have a new algorithm called "growing rectangles" that I'm working out the details of. Speed at this stage isn't as important, since the construction of wall faces takes place at game load.

Software drawing may end up being too slow, even with just a few wall faces. So I might have to revert back to the tile-based lighting for Flash and mobile ports (which I can get up and running pretty quickly once the shadow quadrilateral problem is solved). But the math is fast enough that, if I write a shader to take care of the rest, I could have real-time 3D dynamic lighting in a desktop port... plus a configuration option to revert to tile-based lighting if the player is on a machine that can't support shaders for whatever reason.

Ask a Question / Re: How to get the alpha value of an actor
« on: June 16, 2017, 10:44:05 pm »
Can you go into preview code and show what line 106 is?

Ask a Question / Re: Sorta a list by largest to smallest?
« on: June 16, 2017, 04:37:25 pm »
I thought there was a list utilities extension that provided a block for this? If not, there is a sort method for the Array class that you can call using raw Haxe code:

Pages: 1 2 3 ... 91