Merrak's Isometric Adventures -- Artificial Intelligence!


  • *
  • Posts: 1426
AH! That explains a lot. I was only using it for 'pure' grid based system. Didn't even think about rotating / overlapping grids.

What about stacking the algorithm? So first determine if there is a DC or EC tile and then zoom in that tile and create a virtual grid so that the EC has a clear path and DC is blocked. You might need to experiment with the gridsize in that virtual grid but it might help you. But knowing your background you probably grab another beautiful algorithm out of your teachers-bag !!!!

Thanks for explaining!
Hanging out in the Chat:

Proud member of the League of Idiotic Stencylers! Doing things in Stencyl that probably shouldn't be done.


  • *
  • Posts: 2016
I hadn't thought about a recursive zooming-in approach. That's a neat idea.. If the virtual grid was permanent, I think it would work better. The downside to creating anything is that it turns into garbage to be collected when the process is done. That was one of the big issues I had with Box2D raycasting--the hundreds of thousands of leftover b2vecs that tied up the garbage collector.

Overall I think virtual grid approach would be slower and consume more memory, with the exception of something really neat--large outdoor areas with non-uniform floor heights. In that scenario it would be easy to generate a height map using bitmap data. I think it's worth playing around with  :D  ... but not for this game. As tempting as it is to experiment with that, I need to commit to the feature set I have or else I'll never get away from feature creep.

It's still a bit too early for me to be thinking about line of sight just now. What I primarily need that algorithm for is rendering shadows, but at the moment I don't have anything to draw shadows on...

yet ;)

Here's what I'm thinking-- modify one of the classic flood-fill algorithms to fill in the triangle segments so that I identify entire walls. Internally, it would look something like this

(This is an entirely hand drawn image, so I didn't take the time to fill in every triangle... but I think it gets the point across)

I think it will be pretty simple with the exception of the stairs. The stairs don't fit neatly into any triangles because their planes aren't orthogonal to any of the coordinate planes. So that's a bit of a bummer, but I'll think of a work-around for that eventually.


  • *
  • Posts: 2016
The Face-off

I'm getting close to finished with the flood-fill implementation, including (I hope) those pesky stairs. The nice thing about solving the stairs problem is that if I want non-orthogonal wall planes in a future version of the engine, I will be well on my way. In fact, I realized many of the problems I have to solve stem from wanting to use a tile-based scene editor. I could also enter the wall faces some other way.

Once I move away from Temple of Idosra, I want to revisit the roguelike (or is it roguelike-like?  ???) concept. Tile-based levels seem easier to generate.

But--on the topic of faces, there's still one last problem to solve... the final boss: Drawing shadows on the walls. Wall faces act like a canvas. Once I get the canvas, I need to know where the shadows lie.

This is a tricky problem to solve. It's been solved in 2D a few times. Here's a good example:

I have yet to find an example of a solution to the 2.5D variation of the problem that didn't use a 3D engine... probably because it's much easier to just use a 3D engine. But I think I can get better performance using a 2D engine and adding just the features I need to get 2.5D, rather than using a 3D engine and "wasting the other .5D", if that makes any sense  :P

Since most of the scene data is in 2D, my plan is to compute the shadow locations in 2D in step one, then the height/z-location of the shadows in step two. Step one is more complex, since this is the step where I need my replacement for Box2D raytracing.

To begin, let's figure out where the shadows intersect the wall face planes. Intersections with planes orthogonal to the XY plane (the floor) seem easier to handle. I've yet to work out intersections with the floor itself, but one thing at a time.

These are the possible scenarios in which a wall will cast a shadow on another.

It makes more sense if you saw this demo and the corresponding code:

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

One line segment is a ray projected from the light source and through one edge of a wall face (for this example, let's use vertex A). The other line segment is the wall face itself. t is the location along line AB. If t lies between 0 and 1, then the ray intersects the wall segment.

Just looking at this I realized I left off the case where the wall casting the shadow is smaller than the one being casted upon. That should be tLA  is in [0,1] and tLB  is in [0,1], which is a variation of Case 3.

The annoying thing about working on this will be debugging both the code and the math, since I wouldn't be surprised if I left off a case or two. At least I set up the "edmap" utility. An appreciable fraction of my development time has gone into debugging tools (like the map viewer, image viewer, node viewer, etc.)... but I couldn't imagine doing this without those tools. When something goes wrong, there are just too many places to need to look.


  • *
  • Posts: 2016
Despite running into a few more bumps than originally anticipated, the modified floodfill algorithm is working pretty well. I tested it against a variety of rooms and it correctly identifies entire walls.

Oddly enough, I didn't have a working room with a staircase. All the old rooms haven't been updated to load properly. But I got the goat statues to highlight. If the statues highlight, then the staircases will, too.

I'm pretty happy with the way this came out. I originally was about to write this off as a silly idea, but not only does it generate all the walls, but it generated walls for all of the currently implemented 60 rooms in 2 seconds. It also doesn't require that every image fit perfectly inside a triangle in the triangle grid... but the tiles that the images are anchored to do. So this still only works for a grid-based system, even if the grid is only internal and the images hide it. You won't be seeing any Doom or Wolfenstein clones with this, since the triangle grid assumes a fixed camera and isometric perspective.

While this is a successful test, it does need some tweaking. It correctly interprets the tile properties, but I need to adjust the tiles themselves. For instance, the floors by the windows are technically part of the window tile. I need to separate them, which should be as simple as making some new tiles. That can be put off for now. I don't want to redo any art assets until I know what other adjustments will need to be made.

Generating the walls was the last pre-game loading task. There are two more steps, but these will need to run in-game... which means speed is essential. I need to draw shadows and then merge them with the lighting to create the final lighting effect. The shadow task is a tedious linear algebra exercise, and I'm not sure I outlined the best solution in the previous post.

The best way to describe the problem is that I don't want to be constrained by the same limits as Wolfenstein 3D: flat floor and ceiling, only 90-degree angles, and no height variation. I previously outlined a 2D solution, but that probably won't cut it.

Code: [Select]
Modified Floodfill Algorithm. Assign a "color" to each tile's face plane representing which unique wall the plane
corresponds to. Floor tiles have only one face (parallel to XY plane--the floor). Pillar tiles have one
or two faces orthogonal to the XY plane.

Purpose: Create a canvas for each entire wall to draw shadows and other lighting effects on.

1. Initialize a 2D array of triangles, represented as "buckets" (arrays)
2. For each tile in the scene, determine the top-most tile in the stack of tiles drawn on top of each other (Drawstack)
3. For each tile face plane, place a pointer to it in the bucket for every triangle the tile's face plane covers
4. Create a new array T and place a pointer to each triangle in the array. Set current_color to 0
5. While T has uncolored triangles that correspond to walls
    5A. Pick t, an uncolored triangle
    5B. Initialize an empty array N and push t into the array N
    5C. For each neighboring triangle:
        5C-I. Set n to be the first element of array N and remove n from N.
        5C-II. If the neighboring triangle is uncolored, corresponds to a tile face plane, and is on the same wall* as t,
               then color it as current_color and push it onto the array N
    5D. Repeat step 5C as long as array N is non-empty
    5E. Increment current_color
6. Repeat step 5 as long as there are uncolored triangles that correspond to walls

* To determine if two tile planes correspond to the same wall, look up what coordinate plane it is parallel to (XY, XZ, YZ).
If the two planes are parallel to the same coordinate plane and have the same "other variable" in common, then they make
up the same wall. (For example, two neighboring XY tile planes should have the same Z coordinate)

« Last Edit: May 31, 2017, 11:26:44 pm by merrak »


  • *
  • Posts: 2016
Game Design Document

I'm beginning to realize I should've created a game design document for Temple of Idosra from the very beginning. I had something like it during the "Spooky" Stencyl Jam 16. I spent half the jam period with no power after Hurricane Matthew, and making notes gave me something constructive to do when the sun went down and my laptop batteries died.

I do keep pretty good notes, but they're poorly organized and I often waste a lot of time trying to find where I had written something down. Half my notes are on scraps of cartons, napkins, or other whatever other odd bits of paper I can find when an idea strikes.

Still, it seems strange to have a "proper" game design document when I'm a one-person show, but I found a template online, started filling it out, and it has done a lot of good toward organizing everything and visualizing the final product... which is definitely a good thing when I get stuck on little details.

One of these details is the shadow projection system. I definitely underestimated the complexity of it. I thought the triangle flood-fill would be a lot harder... but, nope  :o

Here's the problem: determining what the coordinates of a shadow are, and whether or not one needed to be drawn. The latter problem was the most surprisingly difficult. The shadows and walls are rectangles, so I figured I'd just use an AABB overlap test. I didn't know AABB meant "axis-aligned boundary box", so how to line up the shadows with the axes?

If it weren't for the stairs, it'd be a simple problem to handle case by case. But because of those stairs, I had to solve the more general problem. I could've reworked the game to have no stairs, but that felt like cheating. Besides, I can have more elaborate levels if I am not restricted to 90-degree angles like in Wolfenstein 3D.

So if I can't change the walls to be aligned to the axes, I have to change the axes themselves. If you have a linear algebra background then you might see where this is going: change of basis.

I actually had to pull out Mathematica to solve this one. As usual, I thought I'd share it here. But--it's really long. So I put it in a PDF. If you have a linear background, or you don't but want to learn some linear algebra, then it may be interesting to look through... especially if you want to perform fast AABB overlap detection on 2D planes in a 3D space.

I also put up the beginning of the game design document, because why not :P. I pulled the template off of Game Development Resources Page (David Arcila).

« Last Edit: June 07, 2017, 11:33:09 pm by merrak »


  • *
  • Posts: 2016
Here's a question with no answer--which is "better": code mode or design mode (blocks)?

The rendering code is quickly snowballing, which I really don't like. The vocabulary I chose doesn't help: wall plane, tile plane, wall face... I think it's a symptom of a larger issue: not correctly visualizing how all the pieces of the code will fit together. As a result, I find myself frequently re-writing code.

Vallas Engine is huge... half a megabyte of code now. For comparison, the version of the Stencyl engine I'm on--B9180 (not counting external libraries like polygonal and Box2D) is about 750KB. So it's a lot to memorize.

The big advantage to blocks is that blocks have a clear description of what they do and can be selected from a palette. Typing is faster than click-and-drag, but you lose that advantage if you have to continuously dig through your files to find the right function. I suppose I could find a more sophisticated text editor, but I like medit.

On the other hand, here is one calculation used to the shadow projection computation. Imagine putting this together with blocks.

Code: [Select]
v0_z * v1_y * p_x - v0_y * v1_z * p_x - v0_z * v2_y * p_x + v1_z * v2_y * p_x + v0_y * v2_z * p_x - v1_y * v2_z * p_x - v0_z * v1_x * p_y + v0_x * v1_z * p_y + v0_z * v2_x * p_y - v1_z * v2_x * p_y - v0_x * v2_z * p_y + v1_x * v2_z * p_y + v0_y * v1_x * p_z - v0_x * v1_y * p_z - v0_y * v2_x * p_z + v1_y * v2_x * p_z + v0_x * v2_y * p_z - v1_x * v2_y * p_z ) / ( v0_z * v1_y * v2_x - v0_y * v1_z * v2_x - v0_z * v1_x * v2_y + v0_x * v1_z * v2_y + v0_y * v1_x * v2_z - v0_x * v1_y * v2_z


  • Posts: 511
I remember you made Temple of Idosra for Halloween. Out of curiosity, are you still doing something with that particular game or was that more of a demo on your isometric mechanics you've been working on here? Are you working on another full fledged isometric game or are you trying to perfect this isometric stuff? Where are you in terms of stability for these mechanics? Details? Goals? Release?


  • *
  • Posts: 2016
I remember you made Temple of Idosra for Halloween. Out of curiosity, are you still doing something with that particular game or was that more of a demo on your isometric mechanics you've been working on here? Are you working on another full fledged isometric game or are you trying to perfect this isometric stuff? Where are you in terms of stability for these mechanics? Details? Goals? Release?

One of my goals with the design document process is to pin down the details of my plans, but generally I'm still revising the original Temple of Idosra from October, putting in the rest of the details I didn't have a chance to put into the original game. The two biggest differences would be the level layout and the graphics. The 6-color graphics were mainly chosen so I could complete them in the time limit. I might do something with those too, though. I haven't settled on that. I have one full game in mind, but also some ideas to experiment with.

They're all held back by one issue though... which I think is best illustrated with the following question: Where is the ball in this room?

I've spent a lot of time working on shadows, and a large part of that is because I think they're really necessary to help the player visualize the room correctly. In isometric perspective there is no vanishing point, so objects both far and near appear the same size. How can the player tell how far back something is? That information has to be delivered somehow, and I think the original game suffered because it was missing.

The original game seemed to be pushing the edge of acceptable performance, too. I got a few comments about slow room transitions, etc., but it was probably still okay. I was making pretty good progress until I got a few complete areas done and started playing them. Adding lighting set performance too far back. Loading times were unacceptable and transitions were very laggy. I took a look at the core systems and realized I can do a lot better, which is where I am now.

It seems like every year I end up rewriting the core components of the game engine, but that's largely due to it being a learning process. I could've used a 3D engine from the start, but I find solving these problems fun :P ... albeit frustrating at times. Plus, by solving this problem myself, I'll have a game with a unique look and feel. If I used something like Unity, the final product would look like a game made with Unity.


  • Posts: 511
A 3d engine could certainly do this and you seem to wear that "expert" tag very well, but doing this in 2d gives it a certain charm imo that 3d can't touch. To answer your question about the ball.. inherently I see the ball as popping out, but maybe a combination of the 2nd and 3rd ball (drop shadow of the 3rd ball and side shadow of the 2nd ball) seem pretty ideal, but then you gotta take into account the distance and I'm sure you've already been through that. I read there were some issues with ray casting but surely there's a compromise to be made.Anyway, I hope this turns into a large scope game. It's nice seeing your progress on this but it would kill me to not see a full game made from all of this! Your progress though from your first prototypes to Idosra have been astounding so far so I'm excited to see what you come up with in the coming months.


  • *
  • Posts: 2016
I'd really like to release a full desktop game at some point. I can't say I was looking forward to pushing it through Greenlight, but it seemed like the voting process did contribute a bit to exposure. The recent changes to Steam have made me reconsider my "master plan" that I outlined even just a few weeks ago.

I actually went back and played the original October game and I think the graphics had some charm. It feels like a waste to just throw all that out. I really should do something with it, and I'm thinking that releasing one or two smaller games as Flash would help with exposure and marketing while I work on the larger games.

One of my goals with the design document is to think about marketing--something I admittedly haven't thought of much at all until now. Of course, I still have to get the engine running again. I just got all my shadow code to compile and am ready to start debugging.


  • *
  • Posts: 2016
I've spent the past couple of days trying to figure out why the shadows weren't coming out correctly. I'm very glad I tested all the math in Mathematica beforehand, because I could at least know that was right.

But, it actually wasn't. I caught a silly oversight that could've been caught by drawing out a few more scenarios.

Consider the light "L2" casting a shadow of the pillar against the wall behind it. This was the scenario I worked out the math for. Both the part of the pillar being hit by the light and the wall behind it are parallel planes. And in that case the shadow will be a rectangle axis-aligned with the wall. Hence, I was able to use an AABB test to determine if the light even cast a shadow against the pillar onto the wall.

But in cases where the two planes are not parallel (L1), the shadow is a trapezoid. So AABB doesn't work and the result was pretty weird. I got too many shadows for one, but in other cases the shadows went behind the light.

So... oops :P This is what happens when you draw out only one example to test a conjecture.


  • *
  • Posts: 2016
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.


  • *
  • Posts: 2016
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.


  • *
  • Posts: 167
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


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