Merrak's Isometric Adventures -- Artificial Intelligence!

merrak

  • *
  • Posts: 2081
Either the door is looked or there isn't a door in the first place. Why put the door there if you don't want them to go into it?
What if they don't go to this area at all? You made it for a reason! It is a shame if it is never explored.

Maybe I see it wrong and you will lit the doors/room later so player can and need to choose to go  into the other rooms. I don't know.
Anyway, as always I like to read your thoughts and attempts on creating something special!

Whoops--I thought there was something important I had left out. That's what happens when I write at 1 am :)

At the start of the game, the only light comes from windows. Rooms that are deeper inside are only lit by doors neighboring a lit room (like in the room in my previous post). The walls cast long shadows that hide certain exits, although the player can still find them.

Partway through the game there is an electricity generator that the player can restore by finding a missing part. The generator powers lamps in the deeper rooms. The lamps will reveal the remaining sections of the rooms. There are also a few mechanical doors which need power to operate. And since most of the monsters in the game are mechanical, then additional power can also bring new ones to life.

Anywhere I absolutely don't want the player to go early I can block with the usual doors. I like non-linearity in games, but I also don't want the player to tell me the game is unfair because they find areas that are littered with pits that can't be seen.

mdotedot

  • *
  • Posts: 1446
Ahhh! That generator part explains a lot.
Cool!

Have fun creating it!

Hanging out in the Chat:  http://www.stencyl.com/chat/

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

merrak

  • *
  • Posts: 2081
Been busy at work lately, so I haven't had as much free time. I did get one much-needed feature for the editor in, though.

The level that the cursor is on is now highlighted.


Editing the wrong level is an easy mistake to make. It's not always caught until I wonder why there's one tile that is always floating in front of the others, out of place. A floor tile that is one level too high, for instance, will always be drawn on top of the player.

I didn't have this issue so much with Tiled, because each level was set on its own layer. It still happened, though. Highlighting the working level ought to help me avoid that issue.

merrak

  • *
  • Posts: 2081

Sorting Stumper. Drawing order has been the number one problem since the beginning of this thread. But it's pretty much solved (for my purposes, at least). Why come back to it?

While the wall ordering problem has been solved, actors provide an additional challenge: they move. Because of that, their images can't be clipped--at least, not efficiently.

The most obvious solution would be to draw each wall on its own layer, then draw the actor on the appropriate layer so that it is behind/in front of the right walls. However, there's a catch: The walls aren't drawn in order from farthest to nearest because such a sorting doesn't exist. That was the reason why I needed the local dependency-based sorting.

The dependency-base sorting (topological sort) is a great solution for cases where you need to sort planes of different sizes. See the 17 September post on Topological Sort. The drawback, though, is that walls that don't overlap on the screen may not be sorted in the way you'd expect. They're not sorted at all, so their placement in the draw order may as well be random.

Once the walls are sorted, I can clip out the parts that aren't drawn and obtain a tiling. At this point, the draw order of the walls is irrelevant because all of the overlaps have been discarded. But that still doesn't solve the actor order problem because there's no way to define how "far from the screen" a wall is. This problem is discussed more thoroughly in the post I linked above. Bottom line, though, is that the proposed solution won't work.

So, what now? It's a nice warm day today, so I sat outside with a pad of paper and sketched out a couple of algorithms. This is my typical workflow. Interestingly enough, I've done more "programming" on paper than in front of a computer.

My current sorting routine constructs three layers: background, "midground" (call it the "stage"), and foreground. The stage layer is where all the actors are, with most walls in the background and a few in the foreground. Assigning a wall to a layer is a bit of a challenge. Crucial to this process is an "occupiable volume (OV)", which is any three-dimensional subspace that an actor can occupy. If a wall opens up to an OV, then it should go in the stage layer. If a wall doesn't open up to an OV, it should go in the foreground layer. Since, in each layer, actors are drawn on top of walls, the background layer is mostly for cases where the actor goes behind a wall.

This solution works with a catch: No part of an OV should be behind a wall. I didn't think this would be a limiting factor at first, but then I started drawing maps. In my screenshot at the top of this post you can see that even a simple doorway can't be constructed.

I could put the wall in the foreground layer, but then if Marika was standing on the tile 32 pixels down, she would be drawn behind the wall--even though she should be in front of it.

I don't think this idea is a total lost cause. It just needs some refinement.

Here are a few pages out of today's notes book. I'm trying to solve three problems:

1. Determine how many layers are needed
2. Determine what layer to assign each wall
3. Determine what layer to assign each OV


I thought I had it on my first idea. It's similar to the dependency sort in that I'm using the overlaps. It'd be worth defining some new vocabulary here. For a three dimensional solid (or a planar wall in 3D  space), let's refer to the polygon that's drawn on screen as the "On-Screen Projection" (OSP). The OSP for any wall will be a quadrilateral, and for any 3D volume a hexagon.

Consider a vector drawn orthogonal to the screen, projecting from pixel (sx,sy) and into the scene. This vector may cross through any number of walls. For every (sx,sy) coordinate in a wall's OSP, I want to compute the maximum possible number of wall intersections between the screen and the wall.

For example, for the pixel on the floor just under Marika's right foot, the intersection number is 1. A vector from that pixel on the screen to that point in the floor passes through the wall. The vector to some points on the floor pass through 0 walls, and some, like the aforementioned point, pass through 1. So the maximum number is 1.

This number can be computed by counting the number of overlapping OSPs. An alternative solution, looping through every pixel and every wall, would take far too long. (Cubic order).

The wall's layer is set equal to the max number of intersections, with Layer 0 being top-most. So for a simple scene, here are the layer assignments:


Seems okay. Unfortunately, I thought of a situation where this wouldn't work.


The problem is that the little half-wall's (W4) OSP doesn't overlap with anything. So it would be assigned layer 0. But then Marika  (or any actor, for that matter) would be drawn in front of W4. Since W1 is also assigned Layer 0, she would be drawn in front of W1 as well.

To further refine the idea, I came up with a way to assign layers to occupiable volumes. The collision detection uses OVs, so this framework is already established. An OV is defined by projecting a floor wall upward until it hits a ceiling (or goes off the map). All OVs are three-dimensional rectangular solids, and so their on-screen projections will be hexagons. Because they have OSPs, I can assign them a layer. Then I can use the occupiable volume's layer to compute the wall layers for the walls behind them.


Hopefully this works  :o

Just so that there's some more pictures to look at, I got the light editor up and running. I can now add lights using the map editor--the first real feature that Tiled never provided.




mdotedot

  • *
  • Posts: 1446
"
My current sorting routine constructs three layers: background, "midground" (call it the "stage"), and foreground. The stage layer is where all the actors are, with most walls in the background and a few in the foreground. Assigning a wall to a layer is a bit of a challenge
"

When you talk about layers:
* Are these Stencyl Layers?
* If so, how do you get the information from those layers?
* Does your editor put things on those layers?
* Are the things they put in Stencyl actors, and do you set extra actor-properties you use for the sorting?

Hanging out in the Chat:  http://www.stencyl.com/chat/

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

merrak

  • *
  • Posts: 2081
When you talk about layers:
* Are these Stencyl Layers?
* If so, how do you get the information from those layers?
* Does your editor put things on those layers?
* Are the things they put in Stencyl actors, and do you set extra actor-properties you use for the sorting?

I should clarify that I wrote my own layer system. On the surface it's similar to the default Stencyl layers: I use sprites and any actors/images on a layer are child sprites of the layer sprite. But I created a new class that extends Sprite, called "LayerDrawStack". It contains routines and fields that Stencyl's Layer doesn't provide... mainly 3D math macros. I could've just added what I needed to Stencyl's Layer class, but I try not to modify the Stencyl engine because that makes it harder to upgrade to new Stencyl builds... plus I don't want all this stuff in my other games if it's not necessary.

The things that get put into the layers are called "DrawStackWrapper"s, which can either be a wall or a Stencyl actor. The DrawStackWrapper class contains the code that, among other things, can check which object is in front of the other. So this is where the properties used for sorting are housed.

All of the "LayerDrawStack"s are then attached to a specified Stencyl scene layer. It makes for a complicated class hierarchy, but then I can use regular Stencyl actors for things like HUD icons.

Edit to previous post. I worked out an algorithm to determine whether or not a wall is behind an "occupiable volume" or not. It assumes that every OV has a floor. At the moment I can't think of any situations in which it'll fail, but I'm a little worried about floors that aren't parallel to the XY plane (such as stairs).


As usual, a lot of vector and linear algebra. This uses the same projection routines I wrote for shadows, so most of the hard stuff has already been written (and optimized!) I also updated my sector viewer to let me see the "occupiable volumes" (called Subsector class--but 'subsector' was a poor choice of name for what it does. "OV" is more appropriate).

merrak

  • *
  • Posts: 2081

Intersection Dissection. A small update to the algorithm outlined a couple of days ago. I got the projection all worked out, but there's still another problem to solve: counting the maximum number of polygons overlapping a wall. The illustration above should clarify what I mean: There is a point on the white box (representing the subsector/OV) that is covered by 3 other quadrilaterals (representing walls): The orange one, the blue one, and the dark blue one. So in this example, the subsector would be assigned layer 3.

The "depth" of a point is defined as the number of wall quadrilaterals it is contained in, and the "depth" of a subsector is defined as the depth of its deepest point.

In this example, by now I would have determined that all three walls are in front of the subsector. I just need to determine how "deep" the subsector is. I can't compute the number of walls "deep" a subsector is just by counting the number of overlaps. For example, if none of the three walls overlapped with each other, then the subsector would only be one wall "deep".

I do have the point-in-polygon test. I could loop through every pixel in the subsector, then loop through every overlapping region, and count the number of overlapping regions the pixel lies in. While this would return 3, this algorithm is undesirable. That's a lot of pixels to loop through.

I'm working on a recursive procedure that should do the job much faster. We'll see how that goes.  :o

« Last Edit: April 04, 2018, 10:36:15 pm by merrak »

mdotedot

  • *
  • Posts: 1446
You are almost at the full 3D engine level!
polygons, quadrilaterals , vector and linear algebra, depth.

Occupiable Volumes . I never heard that term before. I think you mean a plane (face) where the player can walk on?

The description of your drawing resembles raycasting.

I am looking forward how you tackle this!
Hanging out in the Chat:  http://www.stencyl.com/chat/

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

merrak

  • *
  • Posts: 2081
You are almost at the full 3D engine level!
polygons, quadrilaterals , vector and linear algebra, depth.

Occupiable Volumes . I never heard that term before. I think you mean a plane (face) where the player can walk on?

The description of your drawing resembles raycasting.

I am looking forward how you tackle this!

I think the question, "why not use a full 3D engine?" is still a valid one :P There's still at least one significant feature of a 3D engine that I don't have, nor plan to implement: a 3D camera. If I wanted one, I think using a 3D engine, or extending Stencyl with one like you're working on, would be a serious consideration. The fixed camera lends itself to really fast math in the 3D -> 2D projection. I still have issues with depth resolution, though.

I also think it's worth pointing out that the math and programming didn't start to get really hard until I dropped the restriction that every tile and actor had to be the same size.

Making a simple isometric game in Stencyl isn't very difficult. Dynamic lighting adds an additional layer of complexity. Non-uniform size walls is what shot the math level way up. I'm actually quite a bit surprised at what it took to solve some of these problems with walls. But maybe I'm missing something obvious. It wouldn't be the first time--this has been a learning experience.

"Occupiable volumes" is a term I came up with to describe the 3D space an actor can occupy. If there's a word already accepted by pros in 3D games development, I'm not aware of it.

If an actor is contained entirely within an OV, then its image should be contained entirely within the hexagonal boundaries of its projection on screen. I originally defined OVs for collision detection purposes, but it's also a useful tool to figure out what parts of the screen an actor might occupy. For rendering purposes, an OV serves a similar role that a subsector plays in the DOOM engine.

All OVs are rectangular solids, axis-aligned with the 3D world axis. The current conjecture is that the projection of any OV on screen is a convex hexagon. The secondary conjecture is that the intersection of the hexagon with any quadrilateral formed by projecting a wall onto the screen is a convex polygon. I need to either prove it, or find the conditions for which it's false, since the polygon clipping algorithm assumes that's the case. It's a hassle, but at least I have a good example to point my more applied-minded math students to when they complain about having to learn to write proofs. It'd be a shame to put all this work into writing an algorithm to use a tool that the theory doesn't allow for.

mdotedot

  • *
  • Posts: 1446
" until I dropped the restriction that every tile and actor had to be the same size."

It is your call. It is your engine.

Apart from being  really nice to learn things yourself. And to understand things better it is really good practice to challenge yourself. Although not that productive  ;)

" t's a hassle, but at least I have a good example to point my more applied-minded math students to when they complain about having to learn to write proofs. "

You have that goal as well. So you can use your own engine to teach about the need (AND FUN!) of mathematics .
I wish I had you as my teacher. But then again I'm too slow to make it through an exam. 

Hanging out in the Chat:  http://www.stencyl.com/chat/

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

merrak

  • *
  • Posts: 2081
Apart from being  really nice to learn things yourself. And to understand things better it is really good practice to challenge yourself. Although not that productive  ;)

I think I definitely took the slow route. This thread goes all the way back to 2015!

Update 2. I think I found a neat graph theory based approach, which will save me the trouble of dealing with clipping polygons entirely.

The upside is that I can solve the more general "N layers" problem, which I've mentioned before: If I have N objects to be drawn in order, what is the minimum number of layers I need? Take, for example, actors A, B, and C in which A is to be drawn in the back, B in front, and C in the middle.
Code: [Select]
+-----+      +-------+
|  A  |      |       |
| +---+------+--+ C  |
| |   |      |  |    |
+-+---+  B   +--+----+
  |             |
  +-------------+

I shouldn't need three layers to properly order A, B, and C. I should only need two. I can put B in front, and A and C in the back. Because A and C don't overlap, they can be drawn on the same layer even though they're at different depths.

A complimentary algorithm that determines which layer to place each actor on would be a good tool for dynamically generated levels.

The downside is that the solution requires finding the longest elementary circuit in a directed graph. An algorithm presented in 1975 by Donald B. Johnson should solve this problem, but if you take a look at the paper you'll see it's not a simple algorithm.

So this'll give me something to work on tomorrow.

merrak

  • *
  • Posts: 2081
Depth Dilemna... Update 3! Finally have some good progress to show on this problem. I don't have the walls and actors in the correct order yet, but I do have a demo showing the main algorithm I'll use to solve the problem is working. It took a bit of research, but I finally settled on a variation of the Longest Path Problem. While the general problem is NP hard, the graph representing my walls is acyclic and directed, and so is the simplest case that can be solved quickly.

Here's the example I've been using to test this out, along with the graph representing the order of the walls. The blue box represents the screen area of the OV, and the yellow boxes walls.



Shortly after my last update, I figured out I don't really need to find the longest cycle. In fact, there are no cycles in this graph. Originally, I envisioned an undirected graph in which overlapping walls were connected. It's easier to use a directed graph, where the back wall is connected to the front wall. I already have this graph, which is used to sort the walls during map construction. So I can use data I've already collected.

To determine the depth, three things need to happen:

1. Construct the graph representing the ordering of the walls.
2. Find a topological sorting of the walls (I used Kahn's Algorithm, described in a post from September)
3. Compute the length of the longest path. In my example, it is 0 -> 1 -> 3 -> 4, which has 3 edges

The maximum number of walls that are in front of the OV is 3, and so the minimum number of layers needed to order the walls and OV is 4 (Layer 0 for the OV, and 1 - 3 for the walls).

Playable demo! Follow the instructions to construct the OV and walls. Press 'r' to restart.

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

Note: Quadrilaterals must be drawn clockwise.

mdotedot

  • *
  • Posts: 1446
Got a little off track creating walls.
The last wall is almost occupying the whole canvas. Wouldn't it cover all other walls and shouldn't you check if you need to draw invisible walls. Probably that isn't the issue you are facing and you probably do that check in another part of the code?!?
Hanging out in the Chat:  http://www.stencyl.com/chat/

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

merrak

  • *
  • Posts: 2081
Got a little off track creating walls.
The last wall is almost occupying the whole canvas. Wouldn't it cover all other walls and shouldn't you check if you need to draw invisible walls. Probably that isn't the issue you are facing and you probably do that check in another part of the code?!?

That's a cool screenshot 8)

Invisible walls aren't an issue at this point in the map creation process. Invisible walls, such as the backsides of pillars, don't have wall faces (i.e. visible surfaces). The sorting here is purely for rendering purposes, not shadow casting or collision detection purposes where the invisible walls would matter... I'm pretty sure.

There is a little hesitation because I just started integrating the sorting with the rest of the engine, and I need to make sure I defined the problem correctly. I already caught one mistake. I tested with this image and began thinking about what needs to be adjusted so that the depth returned is "2" and not "3". There's no point on the blue box that is covered by more than two walls.


Then I realized this isn't a bug with the code or fault in the algorithm. The original problem was defined incorrectly. 3 is the correct depth--it would be impossible to render the three walls, stacked in the labelled order, with only two layers. So that whole business about finding the "deepest pixel"--scratch that  :P I didn't think about the case I drew above when I came up with that definition of the problem. The graph is actually correct.

But on top of all that, rendering the walls isn't even an issue here. Walls don't need their own layers. At this stage, they're already sorted in the correct order. I only need to separate some of the walls into layers so that I can draw actors behind them.

Here's the desired outcome: The OV is the bright red box. Because part of it is hidden by a wall, it will need to be assigned Layer 1. The other OVs can be Layer 0, because no wall is blocking part of their view.

The OV is an empty space--so its layer is only used as a means to compute the layers of walls behind it. In this case, any wall for which part of its image overlaps with the OV will also need to be Layer 1. Otherwise, if an actor was standing in the OV, they would be drawn behind the walls that they are actually in front of. Note: Layer 0 is the top-most layer, then 1, 2, and so on downward.


This can get much more complicated if there were other walls in front or behind of the ones highlighted in dark red. In fact, in this image it already is. The player can fall into the water, so it's possible for her to go behind Layer 1. This means the water needs to be Layer 2. But then some of those walls I highlighted in dark red also need to be set to Layer 2.

I just need to get a handle on the correct way to define the dependencies. I now have the graph tools I need. Now it's just a matter of defining the right problem to solve.

Vaibhav Sangwan

  • Posts: 157
It feels awesome to have such isometric engines(soon which will be 3d I guess :) ) in a mostly 2d maker community.
Why not make it a part of Stencyl?