Merrak's Isometric Adventures -- Artificial Intelligence!

mdotedot

  • *
  • Posts: 1472
That is a scary one: " Now it's just a matter of defining the right problem to solve. "
Totally relate to this. Sometimes we debug for hours only to find we are looking in the wrong direction and even breaking more stuff!
Hope you can find your problem!

@Vaibhav Sangwan
I can really talk only about my own stuff, but these kind of non-core engines/libraries are hard to make and to maintain.
If Stencyl would support it natively it requires a complete redesign of almost all aspects of Stencyl. So I don't think this will make it into the Stencyl-core anytime soon.

But that will not stop us from playing with it and maybe even make it available to the community to play with  ;D


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: 2155
That is a scary one: " Now it's just a matter of defining the right problem to solve. "
Totally relate to this. Sometimes we debug for hours only to find we are looking in the wrong direction and even breaking more stuff!
But that will not stop us from playing with it and maybe even make it available to the community to play with  ;D

It occurred to me that the best way to view an "occupiable volume" may not be to think of it as an empty space. Rather, I should think of it like a canvas to draw on--just like how walls are thought of. Then why not sort the OVs along with the walls? This seems like a more natural way to view the problem.

But in my own notes I found where I had already looked at it this way. Back in November I attempted to sort the OVs with the walls. I got the "Escher Drawing" warning.


I dismissed the whole approach then, but now I think I was too quick to do so. The warning suggests the sorting problem can't be solved. That doesn't make sense, though. I just came up with another idea to make it work. A couple things are different this time around: I know more about topological sorting for one. Second, I have a better grasp of what an "occupiable volume" is. I think I had the wrong geometry in my original attempt.

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?

mdotedot said the same thing I was thinking. As of now, Vallas Engine is sitting at 32,759 lines of code. Any time there's a Stencyl update or an OpenFL update, all that code needs to be checked and updated. It's one of the reasons I stuck with Stencyl 3.4 for so long, despite having access to the 3.5 beta. I also had to write my own map editor.

There's also a lot of research that goes into these kinds of projects. I don't know how m.e. spends his time, but more than half of mine is spent researching relevant math, algorithms, programming techniques, and API documentation.

One of the greatest things about Stencyl is that the engine is right there to look at, modify, or even replace. So these kinds of projects are possible. But I think the Stencyl team itself made the right call picking one thing (2D) and working to be the best at it.

mdotedot

  • *
  • Posts: 1472
Luckilly I have not so much lines of code (yet). But that is just my code. The HaXe library is way bigger. I'm not sure how many lines.

The most time spend is actually on the Demo programs. I want to remain closest to the way Stencyl is doing stuff.
That sometimes isn't the way how the 3D engine works.

@Escher: I remember this. Unsolvable? Not with the mathmagician doing his tricks! :D
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: 2155
@Escher: I remember this. Unsolvable? Not with the mathmagician doing his tricks! :D

Well the good news is that I managed to revise the visible wall sorting code so that it sorts both walls and Occupiable Volumes. The test maps successfully constructed without generating the "Escher Error". If it works*, I'll be much more pleased with this solution than last week's version. Sorting everything at once seems like a more graceful solution than a two stage process: sorting the walls, then sorting the OV's in a separate step.

* And now, the catch: While I was able to test and make sure the walls are still in the right order, I wasn't able to test if the the OVs are. The sector viewer utility and the game's actual renderer use slightly different routines. The game renderer (called "SectorDrawStack") is still programmed to expect the old "Foreground / Midground / Background" layer structure. I'll have to modify SectorDrawStack to interpret the new graph.

As is the usual case around here, getting the graph up and running took a lot more effort than I originally thought. Here's the math problem I wasn't expecting: If I have two OVs in a map, how to determine which one is in front?

This is a more difficult problem to solve than determining whether one wall is in front or behind another. That's because walls are 2D and OVs are 3D rectangular solids. Because OVs are 3D and the screen is 2D, I can't reverse-project a pixel on the screen to a point in the OV--the solution to the wall-wall comparison problem.

Eventually I figured out I can view an OV as a box made up of six walls, and use the wall-wall comparison algorithm against those. Since OVs cannot overlap, if any "wall" of OV 1 is in front of any "wall" of OV 2, then the same must be true of any point in OV 1 vs. OV 2. At least, that's the going conjecture. It holds for all the test rooms I sketched out.

merrak

  • *
  • Posts: 2155
Sorting Stumper--Update. I finally got the "Water Room" to render correctly. Here it is with the proper rendering order: Floor -> Marika -> Wall


There are about seven layers in this sector. Moving the actor to the correct subsector ("Occupiable Volumes") was already implemented as part of the collision detection system. So that part came together easily. I just had to get the walls and OVs into the correct layers, which proved to be a bit more challenging than I originally thought. (This is usually the case...)

This is only the first correct room, so I'm not convinced yet that I won't find a few more bugs... but this is a good sign. I can move on to the next thing.

The Water Room is a pretty complicated room. It's not one of the most complicated, but it is far from the simpler test cases I've been using. It has 43 visible walls and 4 OV's. These 47 structures are organized in a graph which is the dependency graph. I figured out Mathematica has a neat feature where it will construct a graph from its adjacency matrix. Being able to look at the graph made it much easier to debug everything.

This is the graph. It's how Vallas Engine (well, the renderer and collision detection parts) sees the room.


The nodes labelled 44 - 47 represent the OV's. The rest represent walls. It's a directed graph where the direction indicates which structure is to be rendered in front of the other. The depth of a node will be the layer the structure should be rendered on.

So if you're writing a walls-based isometric renderer (as opposed to the usual tile-based), here is a general algorithm that will handle rendering order.

Code: [Select]
1. Create a graph. Add one node for each quadrilateral (representing a wall) or hexagon (representing an OV).

2. For each node A and for each node B, determine if their polygons overlap
    2A. If the polygons overlap, determine whether the corresponding 3D structure of A is in front of B, or behind, or neither.
    2B. If A is in front of B, then connect node A to node B.
    2C. If B is in front of A, then connect node B to node A.

3. Write the topological sorting of this graph. I used Kahn's algorithm for this. If the graph is cyclic, return "Fail" (This is what I call the "Escher Error", since the endless staircase will trigger this problem)

4. Compute the depth of each node. I used (ref 1) as a guide, but not the code presented. (ref 2) also is a good reference... a bit better if you haven't seen much graph theory and want a deeper explanation of what's going on.

5. Compute the depth of the deepest node. Call it D

6. Create D number of layers.

7. Draw each wall on the layer N, where N is the depth of its corresponding node.

8. Draw each sprite occupying an OV on the layer N.

Note that 2A, 2B, and 2C are not trivial problems. They are problems I've discussed elsewhere in the thread, though. I spent more time debugging the code handling these three steps than any other part of the process.

Now I have a solution I'm happy with. It's one graph that handles everything rendering related. This solution feels more "graceful" than the previous--the two phase process that felt clunky.

This was one of the final "big problems" in the core engine that I knew I'd have to solve, so it's good to get this one out of the way.

While I'm still working on the map editor and a few other design tools, I've slowly started moving onto the game itself. I worked out more details on a storyline that I think will do well for the episodic format I'm planning on. I've made some further adjustments to the overall map, features list, and stats tables. No release date, but I expect to be done before the heat death of the universe.

References.

(1) https://stackoverflow.com/questions/2525316/longest-acyclic-path-in-a-directed-unweighted-graph
(2) https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

« Last Edit: April 19, 2018, 10:38:41 pm by merrak »

merrak

  • *
  • Posts: 2155
The "Now, What?" Syndrome

This often happens to me after I complete a significant task: Now, what?

I think what happens is I get so wrapped up in solving a problem, I start to lose sight of the big picture. A roadmap/design document can sometimes help here, but it's more of a motivation thing than not knowing what the next step is. I know what needs to be done--it's just a matter of gathering the energy to do it.

While I'm making up syndromes, there's also "Ludum Dare syndrome": the total lack of energy that follows from working 48 hours completing a game.

On the positive side, I realized just how close I am to getting a finished renderer. Here is the "Water Room" again, this time with the lighting code updated to work with the subsector/OV system. There were a few bugs to squash, mostly in the graphics themselves.


I don't really like the way the light looks, but this isn't the intended effect, either. Right now I have three lights defined right in front of the windows. What I want is one light source far away from the windows (sun/moon). At the moment I don't have a way to define a light source that lies outside of a sector's boundaries--but that is just a limitation of the map editor. The renderer code itself can easily handle it.

I have five unique light levels (labelled 0-4). I'm thinking about bumping that up to nine, re-mapping what I have to 0, 2, 4, 6, 8, and using a dithering effect to fill in the odd-numbered levels.

I have a few maps sketched out, but there are a couple chores to take care of before I can start making levels.

-- Doorways: The original Temple of Idosra had an extremely clunky mechanism to detect when the player left one room and entered another. It's more noticeable in the version I have on my profile, which is slightly older than the version on GameJolt. Unfortunately, this buggier version is also the most prolific. Doorways use tile collision detection to switch the scene. In the first version, it's possible to get stuck in an endless cycle of scene switches, since the collision can trigger right when the new scene starts and send the player back to the original room.

This was a quick solution thrown together because of the time limit. I kinda kept patching it as I moved along because it was easier than starting from scratch. But since I now have a new physics system, I have to write a new scene transition system.

-- Actor/Actor collision detection: There is none. This falls under the same physics category as doorways. I haven't dug into my physics code for a while. I made some really strange decisions that I guess make sense, but I don't remember my motivations. It's buried in some design document somewhere, so I'll need to find it and get myself back on track.

merrak

  • *
  • Posts: 2155
Making Actual Maps. I'm getting to the point where I can actually create stuff  :o As I've started putting the map editor to use, I've had to go and make several little changes to the interface. Some ideas sound good in theory but don't work in practice. A couple of things that make life easier:

- Keyboard shortcuts. They're easy to remember if you make them yourself
- Highlighting the level that the cursor is on.
- Multiple grid modes for different stages of map creation. I have a "scaffolding" type grid for defining sectors, and a "flat" grid for building in them.

I made a short video showing the creation of a basic map. It'll be the starting area for the game. Many details are missing since I haven't finished all the sprites and tiles, but I can build the basic structure.

The video is sped up 8x. It took around 30 minutes to create this map. It consists of 12 rooms and one sector per room.

<a href="https://www.youtube.com/v/sJzn1bHFCfw" target="_blank" class="new_win">https://www.youtube.com/v/sJzn1bHFCfw</a>

Stages of map creation:
1. Define sectors. A sector is one area that the camera focuses on. A sector is usually a room, but it might also be part of a larger room. The important aspect of a sector is that the camera focuses on one sector at a time.
2. Build structures.
3. Configure the ambient lighting. This is the base light level for all sectors in a tile.

Things to do:
4. Configure point light sources. I'm planning to automate most of these, such as light coming from the windows or other sectors.
5. Set sprites
6. Set detail tiles
7. Configure chests, signs, etc.

Initially, there are no enemy NPCs in this first map, although I plan to have background noises suggesting trouble is around the corner. Once enemies are "activated", they may start to wander in at random.

Bombini

  • *
  • Posts: 1048
This is very impressive!
I would love to play parts of this.
Thats why i am happy to hear that you are "getting to the point where I can actually create stuff"  :)
Keep your energy!

This is very inspiring.

NickamonPoppytail

  • *
  • Posts: 1020
Making Actual Maps. I'm getting to the point where I can actually create stuff  :o As I've started putting the map editor to use, I've had to go and make several little changes to the interface.

That's great :D

How long did it take you to get to this point?

I've been reading this journal whenever I see a new post in this thread. Keep up the great work!
046 121 116 105 116 110 101 100 105 032 121 109 032 116 117 111 098 097 032 110 111 105 116 115 101 117 113 032 111 110 032 101 118 097 104 032 100 108 117 111 104 115 032 117 111 089 032 046 084 074 032 101 114 097 032 115 108 097 105 116 105 110 105 032 121 077 032 046 117 111 121 032 107 099 097 116 116 097 032 108 108 105 116 115 032 108 108 105 119 032 073 032 100 110 065 032 046 116 114 105 104 115 032 115 105 104 116 032 103 110 105 114 097 101 119 032 108 108 105 116 115 032 109 097 032 073 032 046 110 111 115 032 115 105 104 032 109 097 032 073 032 046 101 109 032 119 111 110 107 032 121 097 109 032 117 111 089

merrak

  • *
  • Posts: 2155
This is very impressive!
I would love to play parts of this.
Thats why i am happy to hear that you are "getting to the point where I can actually create stuff"  :)
Keep your energy!

This is very inspiring.

Thanks! :)  I was hoping to get to work on the other features (tiles, sprites, enemy AI), but I ended up spending most of my time tracking down bugs and things on my "TODO" list that I forgot about.

I really want to start looking at HTML5 and shaders, but if I don't stick to the new features cut-off then I'll never finish. So, that'd be something for Episode 2.

That's great :D

How long did it take you to get to this point?

I've been reading this journal whenever I see a new post in this thread. Keep up the great work!

I forgot exactly when I started on the map editor. It's been a while, though. That time includes development of the UI library, but I'm approaching the point where it'll pay off in terms of saving time.

Here's the map as seen in-game. I need to make a few adjustments to the lighting model, but the basic effect is there.

<a href="https://www.youtube.com/v/rbrRbxk9O38" target="_blank" class="new_win">https://www.youtube.com/v/rbrRbxk9O38</a>

Lighting is sector-based, meaning that a sector is only lit by lights within that sector. In order to produce light coming from another room, I have to figure out how the sectors are connected and place a light in the "doorway". This routine needs adjusting. At the moment, it places the light in the center of the neighboring sector. I want it placed closer to the door so that the light is stronger. There's also still some weirdness with having lights outside of a sector. It's probably not that noticeable... except to me :P Placing lights in the doorway is the simplest fix, and would also give the light a nicer fan shape. Plus, I need to know where the doorways are in order to program the enemy AI.

It's been a while since I looked at the light rendering code. It's a lot more complex than I remembered. I think what I have will work for this game--but a shader solution might be a lot cleaner... especially if I could work out a ray-tracing routine.

To do shortlist: Create a "doorway" class and integrate this data into the map editor. Use it to auto-place lights from bordering sectors.
Fix the automatic placement of invisible pillars. (They're not shown in the map progression video)
Marika is alone. Need to fix that  >:(
On the subject on enemies: Enemy AI needs to be completely redone. It hasn't been updated for the new physics engine. It doesn't take advantage of any graphs, and still assumes Box2D is a thing. I also don't have actor-actor collisions yet.

« Last Edit: May 09, 2018, 11:09:59 pm by merrak »

mdotedot

  • *
  • Posts: 1472
Woa that is impressive performance when you navigate through the rooms!!!

What I wouldn't do is start the player in a dark area :D
Start at position where you are at 0:40

Impressive work mate! How nice to see a bit of in-game action with the new math-approach!




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: 2155
Woa that is impressive performance when you navigate through the rooms!!!

What I wouldn't do is start the player in a dark area :D
Start at position where you are at 0:40

Impressive work mate! How nice to see a bit of in-game action with the new math-approach!

I was a bit surprised just how much of a difference the walls-based approach made to performance. I really shouldn't be, since I did a lot of stress tests before starting work on it--but in the previous generation of the engine, a map this size would be totally unplayable.

The number of actors in this map is one. Well, three if you count the HP and move points bars. There are a few thousand sprites in the map, but only a couple hundred at most are visible at any one time. They're also not moving. I'm just moving the camera.

The math is far more complex using walls than tiles, but being able to have large maps is worth it. My CPU usage running the game, even when moving between sectors, is about 0.50%.

I originally liked the idea of starting the player in a dark area with a single light source to attract their attention. I still kinda do, but there's a problem with it. I have a storyline working in the back of my mind, and it doesn't make sense to start in total darkness. It'd make more sense to start in a room with windows. The room at 0:40 is a good idea, but I foresee that part of the map changing around a bit as I start working on more tiles and sprites.

merrak

  • *
  • Posts: 2155
AI Tuesday. After spending so long on graphics, it's refreshing to pick up new challenges. I recently started working on enemy AI. I even added a shiny new AI menu to the map editor. So what's that all about?


The orange arrows pointing out of the doorways are icons generated where the map handler detected an exit to another sector. The AI engine will use this data to construct a hierarchy of graphs:

- Map-Map Graph showing how different maps are connected to each other
- Sector-Sector Graph showing how different sectors within a map are connected
- Tile-Tile Graph showing how different tiles within a sector are connected

Each map will have configurable AI settings, so I can discourage or encourage certain paths to be chosen by enemies hunting the player. The fun part will be getting the enemies to "talk" to each other, so that they take different paths and form strategies beyond just "hunt the player down".

For example, I can mark dark tiles in the Tile-Tile graph so that one enemy knows to lurk in the darkness while a second pursues the player head-on. This is one reason why light is important to the game. The lit/dark states of each room can alter how enemies behave.

I also fixed all the rendering errors that were in the walkthrough video I posted a couple of days ago. I also realized this thread is now just a bit over three years old  :o So here's where this project was three years ago.


« Last Edit: May 14, 2018, 10:34:30 pm by merrak »

Majora64

  • Posts: 511
Been skimming through the journals and looking at your gameplay and I love what I'm seeing...nice to see your commitment to this game. Couple questions:

For lighting, is it possible to create a torch that generates a light effect? I'm sure it's not a priority, but I'm curious to see if it's crossed your mind and how you would go about it if possible. I think it'd be a nice aesthetic to have pulsating lights or have the light reflect off the walls similar to a torch.

When you transition rooms, how do you shift the camera like that in the direction of the room? Is it a camera shift, or does the level just move giving it the illusion of a camera shift?

Keep it up!

merrak

  • *
  • Posts: 2155
Been skimming through the journals and looking at your gameplay and I love what I'm seeing...nice to see your commitment to this game. Couple questions:

For lighting, is it possible to create a torch that generates a light effect? I'm sure it's not a priority, but I'm curious to see if it's crossed your mind and how you would go about it if possible. I think it'd be a nice aesthetic to have pulsating lights or have the light reflect off the walls similar to a torch.

When you transition rooms, how do you shift the camera like that in the direction of the room? Is it a camera shift, or does the level just move giving it the illusion of a camera shift?

Keep it up!

There are two phases in rendering a room that would play a role in creating a torch (or any light) effect. First, the shadows are computed. Then the images themselves are rendered. I spent most of my time optimizing the rendering phase and I know how many pixels I can handle. I can render the entire screen about 7 times per second and still achieve 60FPS.

To create a torch effect, I'd only need to re-render part of the screen one time per second, so this shouldn't be a problem. (Data from February)

Oddly enough, I never tested the casting phase. I always just assumed it would be too slow, and always had in the back of my mind I'd optimize it one day. I made up a quick test, how long it would take to cast the shadows in each sector. Here it is, with time in microseconds.

Code: [Select]
Sector.hx:381: water-cellar.12  casting time:  277.91us  avg per light: 277.91us
Sector.hx:381: water-cellar.11  casting time:  301.53us  avg per light: 150.76us
Sector.hx:381: water-cellar.10  casting time:  324.49us  avg per light: 324.49us
Sector.hx:381: water-cellar.9   casting time:  668.00us  avg per light: 334.00us
Sector.hx:381: water-cellar.8   casting time: 4938.15us  avg per light: 548.68us
Sector.hx:381: water-cellar.7   casting time:  339.37us  avg per light: 339.37us
Sector.hx:381: water-cellar.6   casting time:  964.99us  avg per light: 482.49us
Sector.hx:381: water-cellar.5   casting time:  766.47us  avg per light: 255.49us
Sector.hx:381: water-cellar.4   casting time:  268.90us  avg per light: 268.90us
Sector.hx:381: water-cellar.3   casting time:  271.30us  avg per light: 271.30us
Sector.hx:381: water-cellar.2   casting time: 1117.36us  avg per light: 186.22us
Sector.hx:381: water-cellar.1   casting time:  900.15us  avg per light: 180.03us
Sector.hx:381: water-cellar.0   casting time: 3989.04us  avg per light: 398.90us

Water Cellar is the map I made in the video and explored in the subsequent walkthrough.  The player starts in Sector 6. Sectors 1 - 5 are the little rooms. Sector 8 is the most complex--it's the room with the moat, windows, and bridges. It's the title card on the video seen in my post on May 9.

The nice thing about shadows is that they can be saved, so I only need to re-cast them when lights or walls move. A flickering torch would just necessitate re-rendering the walls with a new light level, not actually re-casting any shadows. A moving torch, like one held by the player, should be doable. I'd just need to modify the computation procedures so that it takes advantage of the fact that shadows can be saved.

Reflecting lights off of walls would be harder. I've thought about replacing the whole shadow routine with a raytracer, but I think that'll need to be a project for another time.

Room (Sector) transitions are made by shifting the camera. When the map is loading, I draw all the sectors, then hide/show the ones I want based on where the camera is. If you're familiar with GIMP (or maybe Photoshop does this, too), think of sectors like a layer group. The Sector that the player is in is turned on and the rest are turned off.

For Idosra, all the sectors are aligned on a 12x12x4 grid (the size is the max dimension room that can fit on one screen). That's just a design guideline I set to keep the look similar to that of the original game, in which every room was its own Stencyl scene. I have a fair amount of control over how the camera behaves from within the map editor. The camera is actually very similar to the one I created for my Ludum Dare 32 game, "Elemental Castle Adventure". The camera follows the player unless the player enters a special region. If the player is in a region, the camera shifts so that the full region is in view, regardless of where the player is standing within it.