Hi there,

this post is for you awesome thinkers out there. I hope there is anybody who can help my with this dilemma.

Short version: I need help with my AI. I don't know how I could implement this one.

Log version: Here we go.

Basically, Forest Strike is a 2D top down game. All the possible stuff displayed is on one specific block as seen in the screenshot (don't worry, this is an old one - the general handling is the same).

Now the thing is, I need an more or less clever AI.

The characters start in one corner, every one on another field. Game Maker provides Motion Planning in order to navigate from one point to another (as seen in the GIF above). As a human player, I basically know where I want to go and what to do. Like if there is a stone block in my way, I should get rid of it first. The NPC does not know such things and this is my problem. I don't know how to implement this.

Let my start with the basic rules, the game is built on:

* one character per block

* you can not move through solid blocks or characters (characters are handled as solid blocks more or less)

* there are destroy-able blocks and non-destroy-able blocks (each one of them has a different parent like obj_parent_destroyable, obj_parent_non_destroyable)

* you can only move a specific amount of steps (randomly chosen at the start of the round)

* you can destroy a destroy-able block with a bomb

* the size of the bomb can vary

    * explosion goes up, left, down, right based on the size starting from the center (the point where the bomb is placed)

        * e.g. bomb size = 3, position x = 10, y =10: explosion-points: (7, 10) (8, 10) (9,10) (10, 10) (11, 10) (12,10) (13,10) (10, 7) (10, 8) (10, 9) (10, 10) (10, 11) (10, 12) (10, 13) (form of a plus  sign)

    * explosion can not go through solid blocks

* you can have multiple characters per player

* characters are assigned to a specific player

* hit-points = 1 (so basically everything is a one-hit)

* items are represented by bouncing boxes (as always, only one per block)

* you can place any number of bombs during a move phase (the phase the AI should be handled)

* bombs explode during the action phase (no movement allowed)

* after action phase, the next player can move etc.

(If there is any information missing, please tell me and I will append it)

So the basic behavior I want to have for the AI:

* move to an opponents character and bomb it

* get the best way (maybe ignore solid blocks first and use an ideal path???)

* try not to bomb characters of the same player (like placing a bomb to destroy a block which is in the way)

* maybe get items

If anyone of you could help me with this problem, it would be awesome. I would really appreciate it, if you could provide structured info or maybe even pseudo-code.

Thank you in advance,

Lukas

AI is writing down a behavior and then finding the math to simulate that behavior.

For example:

1.) Move to an opponents character and bomb it.

We know the player position as a vector2D(X,Y). We also know the AI position as a Vector(X,Y). You use motion planing to find the path to the player, then move to it. Once in a range from the player, you use the bomb.

2.) get the best way (maybe ignore solid blocks first and use an ideal path???)

Weights work best here. For example if planting a bomb to break a rock takes 4 turns(Plant bomb, move away, move to player again, advance one step) that block can have a weight of 4 and a normal tile a weight of 1(advance one step).

So if the AI has to move 4 or more times to go around a obstacle it will instead remove it.

3.) Try not to bomb characters of the same player (like placing a bomb to destroy a block which is in the way

Using the Bombs vector you can move away from the bomb.

For example if AI is at (0,0) and the bomb is the tile to the left (-1,0) then you can use AI - Bomb = (0,0) - ( -1,0) = (1,0) now your AI moves one to the right, away from the bomb. VectorA + VectorB = Move To and VectorA - VectorB = Move Away.

There will be times when this fails, with the AI cornering it self, especially with large bombs. This is good and makes the AI feel alive, because it can make a mistake.

4.) Maybe get items

If Item is in range move to item. Vector + Vector.

Now your AI will run these four behaviors every step.

Loop( Step1, Step2, Step3, Step4). Changing the order also changes the way the AI acts. Example:

If Move to player(Step1) is first, the AI will chase an item when in range. If Find Item(Step4) is first Step1 will always cancel it out.

Thank you for you reply.

I was not thinking about weights, so thousand thanks to you. Seems like I was overthinking the pathfinding thing.

Regarding the 3rd step, when it comes to placing a bomb, I still have a question.

The problem here is, that you may not have any more steps to move. e.g. you have 3 steps to move and the character just moved 3 step upwards and then places the bomb. In this case, it is not possible to move away from the bombs range. I am afraid, that this may happen way to often and the AI defeats himself before you are in range.

To solve this problem i was thinking about something like this:

if(remaining_steps >= bomb_size) {
	//place bomb and move away
} else {
	//do not place bomb and end turn
}

Now, the thing is that you can obtain items and the bomb size may increase. If the bomb_size is about 7 and the highest amount of steps is 6, the AI would not be able to move. But the thing is, that this case is unlikely. Should I ignore this case and use the solution as described above?

Another thing is the implementation. This seems to be a struggle to me.

I saw something like a command stack, which was pretty awesome. Using the command stack, I can define the commands the AI should do.

e.g. move_up, move_up, move_left, place_bomb, move_right, move_down

Then, if the commands are defined, the character should do every move as described in the stack.

Another way to implement it would be to handle the steps on demand as described in Scouting Ninjas Post in every frame. This may be a lot easier than planning the commands.

Maybe I am overthinking this topic as well and there is an easier method. Any ideas?

15 hours ago, LukasIrzl said:

use the solution as described above?

Go with that. Complex AI isn't better and a AI that is too smart can spoil a game.

If the AI plants a bomb that is bigger than it can run, then let it run away. It's what humans do, we run even if we can't escape.

15 hours ago, LukasIrzl said:

I saw something like a command stack, which was pretty awesome. Using the command stack, I can define the commands the AI should do.

This is often called a behaviour tree. It's what I described with the Loop(Rule,Rule) thing. It's the recommended way of doing AI as it keeps things simple.

Command stack is just a fancy name for a concept use as long as AI has been around. It will end up looking like this: Loop(CommandStack(Rule,Rule)), you will just be adding a extra step you don't need. 

Game AI often works better when simple.

Also have you checked some Boids AI? I find it teaches the concept of AI very well.

Thank you for the answers.

I will try to implement it the simple way, as you mentioned. If I understand that right, should I avoid the "command stack" thing? Going without it would work too (maybe even better).

Actually, I've never heard of Boids AI. I will definitely take a look (or more). I am pretty sure I can learn a lot regarding AI, since I usually do simple platformer AI (walk left and right and eventually hit the player).

Pretty sure that Boids has very little application in this game. It's for steering and flocking.

Also his "command stack" is a sequence of things to do in that order to accomplish the current goal. Has little to do with a behavior tree (which is a 1-step lookahead behavior selector) and is more like the result output from a planner system.

Speaking of planners, while something like GOAP might be relevant here, I'm wondering if it is necessary or if you can get decent results just from a combination of pathfinding to important things and some conditional logic about how to handle obstacles (like the aforementioned bomb problem).

For overviews on some selected AI architectures, start here.

http://intrinsicalgorithm.com/IAonAI/2012/11/ai-architectures-a-culinary-guide-gdmag-article/

5 hours ago, IADaveMark said:

Pretty sure that Boids has very little application in this game. It's for steering and flocking.

Just mentioned it because it's a very nice place to start on AI. It helped me realize that AI isn't some magic thinking brain in a box, that everything is just math and rules.

The hardest part when I started was that I thought of AI as is shown in the movies; a conscious being.

5 hours ago, IADaveMark said:

Also his "command stack" is a sequence of things to do in that order to accomplish the current goal. Has little to do with a behavior tree (which is a 1-step lookahead behavior selector) and is more like the result output from a planner system.

Your the expert on this.

It looks like behavior tree to me but it could be because it's one of the few things I know about. That whole if you only have a hammer thing.

Re-read his bit on the command stack... he was defining a sequence that had been determined by some other algorithm (e.g. a planner). Then, the idea is to execute those commands by popping them off the stack one at a time.

Thank you for all your replies.

To make things clear. IADaveMark was right. My idea of a command stack is to create a sequence. e.g. The AI character starts the round and checks if there is a command stack assigned to him. In case there is no stack (actually, it is more like a "command queue") assigned, I will generate the commands all in this one step. The next time, the character has an stack assigned. So in that case, the character will dequeue the first command and handle it.

The whole thing sounds great, but I think this may be a bit too much. As Scouting Ninja already mentioned, I will try to keep it simple by using the behavior tree.

Boids really have little application in this game, but it may help me to understand the whole AI thing better.

One major problem with your stack is that, while executing a stack over multiple turns, the game state will have changed therefore possibly (likely?) invalidating your current stack -- either because it is now impossible or just plain silly.