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

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?

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/

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.