Merrak's Isometric Adventures -- Artificial Intelligence!

merrak

  • *
  • Posts: 1949
More adventures in AI


So far the Temple of Idosra has been a solitary place. I've thought about several different approaches to NPC AI and finally settled on one I'm happy with. The original game had almost no NPC AI. Enemies made a straight path to the player, even happily walking off of cliffs or darting out of the map. I can do better than that :P

The second generation code, which was where I was about this time last year, had smarter enemies. The code driving them was a mess, though--lots of booleans and if wrappers. I used a few dozen boolean "flags" that configured what the enemy would behave like. Don't follow in my footsteps there. When something goes wrong, it's almost impossible to debug the code with that many states to keep track of.

In the MUD server I wrote (which was in C), I had a neat little system set up. I had a function pointer called "act" or "do", something like that, which was called by the game's update loop. I could customize NPC behavior by changing what function "act" pointed to.

I think it's a more natural way to view simulating thought processes. Let's say, for example, we have a driver who sees a deer in the road. Call it a "stimulus function": sawDeerInRoad. There are multiple reactions someone might take. One brain might steer the car into the opposite lane. Another might steer off the road, and a third might just plow into the deer and hope for the best.

I grew up with procedural programming... QBASIC, Visual Basic 3, and later, C. Object oriented programming isn't something that comes natural to me. You can see that in the extensions I've published. The AI system I've come up with is my first real opportunity to take advantage of some of Haxe's object-oriented features.

I suppose I can call it the "stimulus-reaction" AI model... contrasting with the typical "maze of booleans" I usually come up with. I think it'll make it a lot easier to write complex AI routines and, most importantly, debug them when they break.

Here's what I have so far. There is a "general brain" class that houses four functions: think, identifier, message in, and message out. Identifier just returns the brain's name for debugging purposes. The others are where the action takes place. They're overridden by a "specific brain" class, from which I'll have multiple to choose from. The particular "specific brain" will reprogram what these four functions do.

The most important function is 'think', which is just a cute name for the 'on update' function that is called every engine tick. It processes a stimulus queue, which is a priority list. In it's basic form, the NPC can react to time passing, seeing the player, colliding, etc.

The fun part comes in when another NPC sends a message, such as "go to position (r,c)". If this message is higher priority than 'see the player', then the NPC will totally ignore the player.

The first idea I'm going to experiment with is to have two kinds of NPCs: call them "Pawns" and "Masters" for now. Pawns simply attack the player on sight, unless they're given another instruction. If a pawn sees the player, they'll move toward them. As the name implies, they're not much of a threat on their own. At the start of the game they might put up a decent battle, but their low level and low HP makes them easily disposed of.

The real power of the Pawns is taken advantage of by a "Master". If a Master sees the player, they might instruct other Pawns to move around. One approach would be to put two or three Pawns in a neighboring room, so that the player cannot easily flee. The Master might also instruct Pawns to move in the darkness, so that a few of them can gang up on the player after they're all in position.

It'll take quite a bit of trial and error to get a working system, but I don't like the idea of having difficulty just coming from statistics alone. As the game progresses, I want the player to encounter smarter enemies--not just enemies with higher HP.

Bombini

  • *
  • Posts: 945
This sounds like a very enjoyable approach.
Feeling challenged as a play and overcoming this obstacle which does not have a easy to amster solution is an awesome feeling which devides good games from excellent games.

I especially like in this idea the choice of first adressing Pawns or Masters. The Master could be hidden as well or camouflage itself. This all sounds great and would suit the game very very well.

Just playing with the HP of the enemies is a boring approach as you mentioned.
I am personally not that skilles when it comes to coding as you so i try to go the path of new enemies with new attack behaviours and characteristics to keep it intertesting.

Cheers!

merrak

  • *
  • Posts: 1949
Designing maps to take advantage of the idea has proven to be challenging! I've had some time to let the idea of pawns/masters sit and I still like it--so it passes the 'time test'.  Camouflaging masters is a neat idea :D. I like the idea of using chess pieces as analogies. Each NPC type serves a specific role and behaves in a specific way.

...so i try to go the path of new enemies with new attack behaviours and characteristics to keep it intertesting...

The approach I read you took in 'Space Pirate' sounds like it will suit the game very well. One key difference between the problems we're trying to solve is that (I think, based on reading your devlog) you had a better idea of what the levels would look like when you got to the point of programming NPCs.

I'm just now starting to make maps, and I really only got into that because my brother and his family came to visit. His oldest son is very interested in game development, but at 8-years old, he seems to comprehend making maps a lot easier than programming and algorithm design. So we've been working on that.

I showed my brother some of the test renders I did last year--full color, colored lighting--all more visually impressive than the 8-color, dithered lighting scenes I have now. I'm reminded a bit of the problem Bill Watterson faced when he finally won his battle with the newspaper editors--removing the standard panel structure in Sunday comics (at least in the US). I don't remember the exact quote, but it went something like the freedom to draw what he wanted now came with the challenge of doing so. For me--I finally have the toolset I wanted to design my world, but now I have the challenge of using it to create something others would find enjoyable to visit.

Sticking with the color limitations and room/sector size limitations of the original game gives me some restrictions to work with. Once the game series matures, I can remove them because I'll have other restrictions to give the game a root. Plus, adding more colors and light will give the game a sense of progression. Sure, it's all artificial--but so are so many literature constructions, so I'm hardly alone in the world of self-imposed limits.

Speaking of literature, I finally have a general storyline that meets some important criteria: it's episodic, each installment can end with a cliffhanger, and most important, leaves room for growth and experimentation with new level designs, NPC types, and other features.

RosalinaGalaxer

  • Posts: 140
I'm definitely going to keep a closer eye on this now that your getting into the AI of it. AI just fascinates me. I wouldn't even know where to start if I were to code it, but it's still super cool.

How in-depth do you plan on getting with the AI? Is it going to be like trying to outwit the AI like in Rain World, or do you just have to outfight it?
W̸͚̯̒͗̊̂͗̃ë̴͙̻̣̠͂́͑͘̕̚ỉ̶̱͚̤͕͍̮͛͂̇r̶̲̣̜̳͐̇͋͘d̸͈͎͓̙̔͜ ̵̠̫̜͋̄̔͘͜ǵ̷̯͍̽̍̉͐̽̈́l̶̡̛͎̬̮̮̬̠͌͊̓̇͘i̶̡̻̰̖͕̘̎͊̚t̶̬̬̤̣͌̆͌͐̔̇̀c̷̙̳̙͈̖̀̈̎̋͑̉͜͝h̴̫̀̏͜͝e̷̝͑̊̍͘s̷̥̰̙̠̺̫̆ ̷͈̯̝͘ͅe̸͍̣͇͙͕̖͗̉̓̃̓͌͝v̶͕͕̰̘̙̫͒̑e̷̞̤͍͔͐̽͌̓r̷̨̺̲͊̋͘͝͝y̸̛̱͂̚ẇ̴̨̯̤̠̱̭̣̈̍̓h̶̨̤͎̞͛͋ę̴̻̪̝̙̬̒͜r̵̗̟̼͋ĕ̴̙̬͐͌!̵̱̠̉

“I have never seen a more heated discussion about context, jazz, and cats.” - VanillaButterz

mdotedot

  • *
  • Posts: 1419
Quote
I'm just now starting to make maps, and I really only got into that because my brother and his family came to visit. His oldest son is very interested in game development, but at 8-years old, he seems to comprehend making maps a lot easier than programming and algorithm design. So we've been working on that.

These are things that really test your engine. And should be giving you great insight if the game will be fun.
Iteration over maps will be a great way and hopefully can also present nice challenges for the Artificial Intelligence.

Your approach on the A.I. sounds nice, but I'm not sure if it can be as flexible as you hope it will be. Proof me wrong, please !! :D

As always I enjoy reading your adventures and I'm really interested to see some of the maps you made / or will make!
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: 1949
I'm definitely going to keep a closer eye on this now that your getting into the AI of it. AI just fascinates me. I wouldn't even know where to start if I were to code it, but it's still super cool.

How in-depth do you plan on getting with the AI? Is it going to be like trying to outwit the AI like in Rain World, or do you just have to outfight it?

AI is very broad. I take a graph-based approach to it, which is well suited for games. A good place to start, if you're interested, is graph theory. A* gets a lot of time in the spotlight, but there are other algorithms that solve graph-related problems. I've mentioned a few of them previously in this thread, albeit applied to solving graphics rendering problems and not AI problems.

The world of Idosra I is not nearly as complex as that in Rain World. There's not really an ecosystem to simulate. mdotedot is probably right--I think I have grander plans than I can pull off, or even need to pull off, but I'm going to try, anyway :D

I haven't quite finished the backstory, but it's a sci-fi based story that draws inspiration from The Time Machine and the far future it depicts. What I have so far is that the player is first shown a quick cutscene illustrating a devastating flood (think rising ocean levels) and a cut to a few hundred years later. For reasons I haven't figured out yet, Marika finds herself in an abandoned structure with a flooded bottom floor. She can't read any of the signs or texts, which are in an unknown language.

All of the NPCs are called "golems" (effectively robots), whose builders are unknown. Their roles are also unknown, other than the one that is obvious at the start--as guardians.

When it comes to designing their AI code, I'm trying to put myself into the mind of their builders--how would they program the golems to behave? What limitations do their systems have?

What I have so far is that they communicate by sound. There is a sound-based language the player can pick up on. Since sound can easily distort and deteriorate, I need to simulate errors and along with that, error handling. So the AI code is part of the game world, not just something 'under the hood' that makes it all work. In order to communicate across multiple sectors, they need to set up relays--so there are some strategies the player can employ to disrupt how effectively the golems can summon aid.

That's about as far as I've got. I've already acknowledged that I might have to rework a lot of the maps as the idea matures, but that's okay. I'm now at the point where making maps is easy and an enjoyable experience. Tiled wasn't a bad solution, but it's not really suited for the types of structures I have in mind and so was frustrating to work with.

« Last Edit: June 06, 2018, 08:18:57 pm by merrak »

mdotedot

  • *
  • Posts: 1419
Quote
What I have so far is that they communicate by sound. There is a sound-based language the player can pick up on. Since sound can easily distort and deteriorate,

That 'sounds'  (pun intended) real cool. Maybe you can have the player disrupt the communication between the pawns/golems as to get an advantage.


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.

Majora64

  • Posts: 511
Do you ever go back to your older back ups of this project or your original concept of this journal and go “omg”?

I love the idea of the story(I get a Titan Souls, Botw, ancient technology vibe)  and the potential variety of golems, but it still sounds like its an extremely early concept which is exciting cause it can only grow from here!

The communication and  sound design is interesting. I can picture sound or events being triggered when the player gets within a certain radius (A* like Hotline Miami) or being detected if you interefere between 2 golems communicating via sound waves (maybe some of tbem can be blind golems and a certain section of the game can be dedicated to manuevering around them). Or golems that emit sound waves that can kill you.

Also, is Temple of Idosra centered mostly indoors? I would love to see maybe some type of outdoor area or a courtyard. Also, playable demo???  :P keep it up!

Bombini

  • *
  • Posts: 945
...you had a better idea of what the levels would look like when you got to the point of programming NPCs.

Yes that is true and i also constantly adjust the levels to keep the "AI" and levels in balance (plus the storytelling of course). All has to support each other.

merrak

  • *
  • Posts: 1949
That 'sounds'  (pun intended) real cool. Maybe you can have the player disrupt the communication between the pawns/golems as to get an advantage.

That was one thought I had. Designing maps to take advantage of this could be challenging, though. I think it'll take a lot of playtesting to tune it in, but would be really neat if it worked.

Do you ever go back to your older back ups of this project or your original concept of this journal and go “omg”?

I love the idea of the story(I get a Titan Souls, Botw, ancient technology vibe)  and the potential variety of golems, but it still sounds like its an extremely early concept which is exciting cause it can only grow from here!

The communication and  sound design is interesting. I can picture sound or events being triggered when the player gets within a certain radius (A* like Hotline Miami) or being detected if you interefere between 2 golems communicating via sound waves (maybe some of tbem can be blind golems and a certain section of the game can be dedicated to manuevering around them). Or golems that emit sound waves that can kill you.

Also, is Temple of Idosra centered mostly indoors? I would love to see maybe some type of outdoor area or a courtyard. Also, playable demo???  :P keep it up!

The idea of a flood came from the fiasco getting the first game finished.

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

The full story is in the original game's announcement thread, but the short version is that development was interrupted by Hurricane Matthew.

It's weird to go back and look at the older screenshots :P I'm pretty sure I contradict myself in several places ("X can't be done", "X won't be hard", "X should only take a few days", etc.) I like to share technical details of things I learn, but this is definitely a journal, not a "how to" guide for anything.

I have a "gardens" area, but at this point it doesn't stand out visually from the indoor areas... at least, not much. The engine really is optimized for indoor structures. CPU usage is a function of the number of polygon faces rendered, not the number of tiles. My engine might struggle with maps like what Dincicode is doing in his NC Tactics video series, which is a worst-case scenario for my renderer: no tiles can be merged because they're all at different heights. I haven't really tested it, though.

I keep hoping to get a playable demo up soon. I've given up on Flash--so maybe HTML5. The map editor doesn't work at all on Flash, and the game renderer works slowly.

« Last Edit: June 08, 2018, 09:33:28 pm by merrak »

merrak

  • *
  • Posts: 1949
720p Upgrade Special!

After a much needed vacation, I'm back to work. There's a myriad of things to do to get AI working, one of which is giving the NPCs something to do. Where I last left off, I had just gotten the physics of actor-actor collision detection and resolution working. Physics aside, though, there was no mechanism for collision response. Since I've basically written the entire physics engine from scratch, I can't use the Stencyl collision events. So I wrote everything I need to tell the NPCs (and player) when hit boxes collide. So now I have something that's starting to resemble a game! :o


Currently the NPCs register hits and react... but their only reaction is shouting that they're hit into the log viewer, so their screams are still unheard

Code: [Select]
[Temple of Idosra 5] VActor.hx:942: [Actor 2,Golem 1] says good bye World
Observant readers may have also noticed something else... the aspect ratio of the screenshot changed! I've converted the game to 720p. Really it's 640 x 360, but then scaled 2x to give the full 720p screen. At the moment the decision is more symbolic--a sign of shifting away from the original Flash vision. But I do have a new practical problem--dead space.

My standard 12x12x4 rooms fit neatly in the original 768 x 640 window. Or, rather, the window was chosen to neatly fit the room.

Already I have plans for the extra space in the map editor. As I've been using it for real level production, I've identified bottlenecks in my workflow. The extra space will go to good use putting the tools I use the most out in front so I don't have to dig through menus and options to get to them.

For the game, however, the use of the extra space is a bit more of a mystery. I have some ideas, but nothing solid.


I like keeping the HUD and other UI elements to a minimum. But, say for example, putting inventory cards in the margin when inventory is selected, rather than blanking out the screen to show the cards, would be an improvement. Below is the current (bland) inventory screen.


The margins in the main screen are now 256px on either side. That's plenty of room to show the cards and the room. In fact, I can shift the room 256px to the left and have a 512px by 640px area to show options, inventory, etc--almost the size of the original full screen I was working with. Plus, having inventory cards and the room in view would make it easier for the player to perform actions on room objects with inventory objects.

Upgrading to 720p was a terrible experience and I hope I don't have to go through anything like it again (but I know I will). There was a lot of legacy code getting in the way--much of it a holdover from the original game. I've told the story a few times, but for anyone who hasn't heard it, the original game had a 10-day deadline, five of which I lost to Hurricane Matthew and the resulting power outages.

So how do you program a game with no power? Answer--text files! I had a laptop with a spare battery, but compiling drew too much power. So I typed everything in text files and later wrote code to parse them. This lead to some really weird design decisions and I knew they were bad, but changing them would mean inevitable bugs and that's time I wouldn't have to work on something else. You know that feeling when you're driving and you see something in the road but you know you don't have time to safely swerve out of the way. You have to plow into it and hope for the best because the alternative is driving into a ditch.

Things are working now, though. This leads to the next step. What is it?

Well, back to AI. The NPCs just stand there and take hits, so that needs to change. The most important upgrade is that the state manager now works again. If you're familiar with the Animation Manager from the Jump and Run Kit, you can imagine the state manager works similarly. It's original purpose was to manage animations, but it also manages what effect is mapped to each action. For the player, this means what the action1, action2, etc. keys do. For NPCs, this means how instructions they might be given (say, from the AI engine) are to be interpreted.

This is very important to the AI system, because an NPC can receive an instruction at any point. The state manager will allow me to have an NPC either react to an instruction, or make a note--stash the command in their memory--to handle it later if they're in the middle of something else.

The NPC's memory is a part of the AI system I should talk about more, because to me it's one of the more interesting parts. How do I get my NPCs to remember things? It's actually pretty simple... right now. These things usually blow up in complexity as more required features are identified, so it's probably too early to go into much detail. I've gone on way too long anyway, so that'll be an update for another time.

« Last Edit: June 18, 2018, 11:14:30 pm by merrak »

mdotedot

  • *
  • Posts: 1419
Quote
You know that feeling when you're driving and you see something

Just this morning : Ducks .. why don't they fly? ... 5 of them walking behind eachother ....

I didn't had much speed so I could stop ~~~~~~~~

------

So you are going for a Finate State Machine approach?
Wouldn't behavior trees be more inline with NPC s?

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: 1949
Quote
You know that feeling when you're driving and you see something

Just this morning : Ducks .. why don't they fly? ... 5 of them walking behind eachother ....

I didn't had much speed so I could stop ~~~~~~~~

------

So you are going for a Finate State Machine approach?
Wouldn't behavior trees be more inline with NPC s?

I'm probably going to end up with a model closer to Utility AI, something I've been reading up on recently. A behavior tree could get very complex, and I have some good tools in place to build a scorer.

In particular, using the sector-sector graph, I know how much time it costs to move from any one room to any other room.


So here's a hypothetical scenario. I have two NPCs and both are told what room the player is. They want to take two separate routes. NPC1 computes the cost to move to the room and so the scorer assigns that cost to the action "Move to Player Room using lowest-cost path". When it is NPC2's turn to move, the scorer assigns a penalty to the best path, so that the next most attractive option--use the second best path, is chosen.

I can tweak this idea further by assigning a penalty for each room NPC2 travels through that NPC1 will travel through, thus encouraging NPC2 to take a totally separate route if possible.

Each NPC has a library of actions to choose from, designated by its state or instructions received from a "superior" NPC. Using the scoring system, I can throw in other alternatives, such as waiting, meeting up with another superior, etc.

The problem with a behavior tree is that the list of actions is not constant, so I'm either making lots of modifications to the tree or parsing a lot of nodes that shouldn't apply. A simple list will be a lot easier to manage than a tree.

mdotedot

  • *
  • Posts: 1419
Wow .. that looks like a step to a neural network. I'm going to read up on that link! Thanks for sharing.

25 years ago I had an idea that I still need to turn into a real thing: evolution based problem solving.
Not quite a neural network but using ' code ' which you can think of as DNA.

The problem with these kinds of things are the 'world'  which scores the generation.

You seem to have found your ' scorer ' . Excellent: that gives you the ability to generate or decide what best to do for that particular moment/stage.
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: 1949
25 years ago I had an idea that I still need to turn into a real thing: evolution based problem solving.
Not quite a neural network but using ' code ' which you can think of as DNA.
The problem with these kinds of things are the 'world'  which scores the generation.

I took a course in genetic algorithms one summer. I thought it'd be neat to use in a game to determine NPC behavior, but the problem with these kinds of algorithms is the number of 'generations' needed to trend to a useful result. The project I was assigned was to solve the knapsack problem, and it took a few thousand generations to "grow" a good solution to the problem.

Genetic algorithms was still kinda new back when I took the course (2006). Not sure what AI applications there are, but 12 years is a lot of time for development and research... so I wouldn't be surprised if there was something.