Keeping the distance

There has been a long weekend but I have implemented a distance check. This will also be the firing range later on. It was really simple. It is an new integer member of tank’s base class Agent. I call it distanceUnits. I just assign it the number two for now. When I search the path from the behavior tree, I also fill the tank’s path list. The path finding algorithm fills its own path list by adding the goal node and its parents all the way back to the starting node. I add these nodes’ positions to the tank’s path list backwards from the end of the first path list to the front of it and I simply stop the loop before the tank gets the position of the goal node. Since the distanceUnits variable equals two, the tank’s path list stops three squares from the goal. (Of course, the 0-th index in any list is the first element which means it naturally stops three elements from the start element if I let the loop stop when “i” is not greater than two).

AgentDistance.PNG

As seen in the picture, the two blue squares (tanks) have stopped before they have arrived at the enemy bases (red and green squares).

in code it looks like this(read the comments in the code):

https://pastebin.com/2Y6b8SLR

Just a quick post this time. Next up will be the bases and then I will probably need to discuss what to do with them and the tanks to have the tanks destroy the bases. After that I’d probably also want to start adding new types of units. Should be relatively straight forward.

As always, take care of yourself, aaaaaand each other!

(if you know where this expression comes from, comment 🙂 )

 

What next?

As the title suggests, I am not sure what to do next. Let me try to see what I want to have.

  • three different characters for each team. They are a tank, a long range shooter and a close combat unit.
  • Tank moves slowly and has a lot of hp. Fires slowly but powerfully.
  • The long range shooter fires from a long distance, powerful shots and low hp.
  • The close combat unit moves quickly, hits hard and has more hp than the long range shooter but less hp than the tank.

Of course, I will have to do a lot of number tweaking and balancing. I should consider migrating this to unity so that I can have builds ported to hand held devices. But since I don’t have a deadline I have time to learn more about BTs. I still have not come to the optimized memory storage or the BT using events yet.

When I have anything to evaluate I’ll start migrating everything to unity. Then I can gather feedback relatively quickly. It will also be interesting to use C# more and learn more about it.

I also want the units to have a sense of other units. I am thinking in the long run that they should both help each other if a team mate is near by and change attack priority from walking to the base and attack it to stop and attack an enemy and if need be, change path to follow the enemy, if an enemy is in range.

I need some collision avoidance/detection as well. Regarding the bases and the agents themselves, a simple range check will do. Since I’ve got the path following the nodes I should be able to skip the target node and a number of nodes depending on what unit is currently wandering. For example, the tank might stop 3 tile distances away and the long range 5 tile distances and the close combat unit stops just one tile distance away. Later on I will not want the units to overlap each other (at least not visibly so).

For now I believe I should start building the distance from base feature and then add the attack. This should be the most straight forward step to take because I only need to adapt the tank itself and the way it receives the path nodes. Then it will become more natural for me to add the attacking because I most certainly will need a base class that knows how much it is damaged by the shots and make a note of when it is destroyed. This design will have to be planned carefully because I want to have a smooth way of pulling this off. Right now, I am considering the observer pattern to send and receive the information needed;

“Tank is attacking you with its current attack power!”

“Ok, I withdraw that amount from my HPs.” and eventually; “OOOps, I’m dead!”

Like I said though, first the distance from the base must be solved.

Take care now!

Oh BTW, Yes I moved that nasty line of code from the creation of the tanks, the one described in the last post that would potentially cause problems during runtime, I simply broke it off the creation function:

https://pastebin.com/aFC9ERVi

 

 

Multiple Tanks

I’ve got the two tanks now. One is a member of team green and the other is a member of team red. They both walk to different locations and both use the same BT.

There where a few problems but nothing extreme. The following picture will be the last picture of the game world with the nodes drawn. I add this picture as a demonstration of my success in adding another entity and have it use the BT itself.

AgentsWalking.jpegThe picture above shows two blue squares one starts from the top right and the other from the bottom left. they each have walked to their team opponents’ base. The bases are the green and the red square and the blue dots represent the path they took.

 

The following content of this blog will be the functions and short descriptions of them. First there are descriptions and under them are the links to pastebin with copy-pasted code.

Starting from PrototypeState::Enter(): It is very similar to how it looked last time I posted it, but the difference is a new function being called twice, TankStateEnter(point,TEAM). I set the two tanks up in them and assigns each a starting position and a team color.

https://pastebin.com/i4xv0QRV

TankStateEnter(point,TEAM): It allocates memory for a new tank, give the tank a team and the location of the enemy base and push it back into an std::vector. The tankIter is an std::vector<Tank*>::iterator. and this little one is a potential for undefined behavior! this is ok FOR NOW since I set it before the game loop and the two times I do it will not change any thing.. However, if I use this function during runtime – imagine: in the midst of battle, a new tank must be spawned, spawning a new one would reset the tankIter and make it start over from the beginning. Say there are 100 tanks. The tankIter is at the 50:th tank and the BT is moving it around. Next frame, tankIter gets reset and the next tank to be guided by the BT is not the 51:st tank but the first tank again. If that wouldn’t crash the program, it would make the rest of the 50 tanks miss updates. I WILL fix this potential problem before I proceed with anything new.

https://pastebin.com/tMu2Q3FA

Jumping to the next relevant function: FirstBTFindBase::RunTheTree() it just calls the child’s of the root node, which is the sequence node, initialize function and its update function. The initialize function only resets the currentChild pointer to its children to point to the first element of the children std::vector. I didn’t think one line of code was worth copy-pasting.

https://pastebin.com/8kWtbVCm

Next function is the update function in the sequence node. This is totally untouched by me, it is exactly as I found it in the BTSK. What is going on here is that the sequence try if all of its children, one by one, is returning the success status enum. in this case all the children are leaf nodes and only either checks a bool or makes something happen. In larger, more complex trees, the children might be sequences or other types of non leaf nodes and have children of their own.

Anyway, if any child returns fail or running (not complete with task) the sequence returns this status to its own parent and the next frame it starts over again. When all children have returned success, the sequence can finally also succeed and make his parents proud.

https://pastebin.com/TJbJ8Jk3

One last function before my own implementations are described. The tick function. it initializes the current child if necessary (mine is just an empty function) if its status is NOT running. It then accesses the current child’s status update function. if that does not become running it terminates the child (again my terminate function is also empty) and returns the current status.

https://pastebin.com/YmeTWES8

Now we enter my custom nodes’ update functions! They all have that same blackboard as set by the ServiceLocator in PrototypeState::Enter(). The blackBoard has friend access to the game world to be able to check everything that is going on in there. (some “friend”, huh?) It can also directly manipulate things in the game world. (be careful….) ok so here it will become obvious that the tankIter has to be set somewhere else than when a new tank is created.

First out is ConditionArrived::update(). It checks to see if the tank is at its target location. The IsArrived() function of BlackBoard looks very much like most of the blackboard functions used in the tree as of now. I perform a check on tankIter to see if it has reached its end, in which case it is time to start over. It might be redundant to keep checking this in every function that uses the tankIter but I have used it as a safety percussion while debugging the code.

ConditionArrived:

https://pastebin.com/dA4yhY2m

BlackBoard::IsArrived():

https://pastebin.com/qgSne3e1

Next child, the ConditionBaseWalkable. the update function, very straight forward. check to see if the node at the position of the enemy base is accessible. The two BlackBoard functions GetGoalPosition() and IsBaseNodeAccessible() are presented and described in that order.

Get GoalPosition, return the current tank its enemyBasePosition sf::Vector2f.

IsBaseNodeAccessible, just what it sounds like. By getting the graphobject from the game world, it investigates if the node in the position is accessible.

ConditionBaseWalkable:

https://pastebin.com/SLyP6ztP

BlackBoard::GetGoalPosition():

https://pastebin.com/AytwY9fX

BlackBoard::IsBaseNodeAccessible():

https://pastebin.com/ugGsAzhy

Ok the resent ones have been a little dull so I will refresh your sore eyes with some more code; The first action node, ActionFindPathAndGo. this one is a little more interesting because it does two things, find path and give the tank its path to walk. (I have a discussion about this a few posts ago, sometimes you might want to find the path but not immediately start walking it)

I first check to see if the searching bool is true in which case the node returns running. (the bool is true when the tank has a path and while it is walking the path.) If this is not the case, I get the position of the tank and the tank’s enemyBasePosition. Those are used to find a path and if the path is found, the tank’s searching bool is set to true (to stop the tree from starting a new search while the tank is walking) and the tank’s pathlist is filled.

I am only going to paste the ActionFindPathAndGo::update() because I have limited pastebin pastes, BUT I am HAPPY to show anybody any of the functions in this function, just ask!

https://pastebin.com/cCiP69me

And now, the final but most important node, ActionSetArrived. It sets the bool arrived in tank. This is important because this is the initial test condition and now that it is true, the first leaf node of the tree will fail, avoiding unwanted attempts to find paths and walk them.

ActionSetArrived::update():

https://pastebin.com/GceVD93M

Last function for today: the Tank::update(). Here is where the bool searching is reset to false when any path is completely walked:

https://pastebin.com/YyikgyFJ

Thanks and good night, I will return in a couple of days to plan ahead and continue the progress.

Next step

Ok so I have the first BT. To remind you: Check the agent’s arrived at base status. if false the node SUCCEEDS. Yes, simply because if it would return failure or running, the sequence would fail. Then check to see if the base is on a tile which is walkable. Next node in the sequence is finding the closest path to the base AND makes the tank go there.

I do not know if I should split that up, it is actually two verbs: FIND and GO. How ever I think not – when would I want the agent to know the way to where his purpose to go is and then NOT go there? I guess if I need the agent to choose from moving to some location or help somebody first, the agent could need a path to determine if it should go or help  depending on what the overall objective is or perhaps the time it has to go to its goal. When the time comes for such choices I will break these two verbs up in terms of BT-nodes.

Finally when the tank has arrived at the location, the BT sets tank’s arrived member to true. This will make the BT fail at its first condition node – check arrived – stopping the tree from going, well, almost. It still does traverse from root to sequence to condition 1 each game loop. Making a note for future reference.

Now I will add another tank to use the BT, only this tank is going to another base located on the opposite side of the map. I have made an enum:

enum TEAM

{

GREEN,

RED

}

Depending on this enum I will make the tanks go to separate goals using the same BT. I make two bases one red and one green. I make two tanks, one of them assigns the TEAM green and the other assigns it red. Then I check the teams and give them the appropriate goal vectors.

Since I am only going to add another object and assign the team and give the tanks another vector2d member “enemyBase”, I do not expect a visit to #include dependency loop from hell again. A function StateEnterInitialize() in tank could find the bases and assign the teams and positions. The function could then be called from State::enter() ( this function was copy pasted via paste bin in the previous post.).

Yes That’s enough thinking for today. I will go with this plan for now.

 

#include from hell ( BTSK )

Update:

I have come back from a few days (5-8 h/day) of chasing the root #include of the infamous circular dependency loop. I am shaken but my morale is high.

I had a wonderful idea; I was going to make a “BlackBoard” class. It was supposed to have the ability to collect data and enable the path finding alghoritm…

Before I dig into the idea I need to give you a little backstory; I have a class made up in a hurry only to have a window and basic graphics to visualize how the A* behaves. I called it StartPrototype. I handle a lot of things there, the window, rendering, event handling, map drawing and now it also starts the A* and calls the agent’s update function. I will change this later but for now I want to refer to it as GameWorld.

I figured that a BlackBoard class will need access to the GameWorld to let the BT know whether its leaf nodes and branches succeeds, fails or need to return running. What could I do? the simplest way that I could think of was to declare BlackBoard a friend class of GameWorld. Then I could just create the functions needed for the BT in BlackBoard which would in its turn use the GameWorld just as if they were the same, but GameWorld would not reach the members of BlackBoard. Then all that was needed was to give the nodes in my tree an instance or pointer to BlackBoard and I could tailor fit BlackBoard to get the information the nodes needed.

Up until this point, the idea is still simple and straight forward and I still want to implement this concept. The following is what I am going to change and what made my #includes go crazy.

TIME PASSED!!!!!

About 5 days ago I wrote the text above. I sometimes do not complete posts. Now I have implemented the BT! This wasn’t as easy as I wanted it to be but I have implemented it the way I said I would.

I had not been thinking about the includes. The circular dependency was rough. I figured since StartPrototype was handling so many things (described above) and I needed parts of it for the BT such as access to the tile grid and nodes. This meant I included the file StartPrototype.h into the Behavior tree and the Agent (the entity “Tank” that will be manipulated by the BT) and here and there. StartPrototype.h also had included Agent and Behavior tree and so on and so on.. If I would have written a diagram of it it would make a ball of dry pasta tagliatelle look like parallel lines.

I was inspired by what I had written in the top of this post, break down StartPrototype into several classes. StartPrototype should only start the prototype. Then I migrated the window and event handling to my custom class Window. I am keeping it short, I will focus explaination to the BT. Then I made a new class GameWorld. Game world creates the grid and the graph. I also made a new state, PrototypeState, for my state machine.

After a few days of migrating code I had the game running again like before and I started making the needed Tree Nodes. One RootNode that inherits behavior. It only starts the tree. One sequence node that holds a container with the 4 leaf nodes. The sequence runs the children one by one so long as they succeed. If one child returns running or failed, the behavior tree starts over from the root node again.

I had my BlackBoard, BehaviorTree (the custom nodes), Agent and GameWorld in a mexican stand off again. I wrote a sloppy diagram:

DependecyDiagram.jpgAs you can see Agent had behavior tree, that included GameWorld, which included Agent which included Behavior Tree and so on! There could probably be other lines drawn here as well. I did not want to have GameWorld.h included inside BehaviorTree.h because it brought other includes with it. but BlackBoard needed a pointer to GameWorld to access its private members (lol I can’t help thinking that sounds dirty). But it just could not be included at all. The Behavior Tree needed BlackBoard, and blackboard brought with it GameWorld and there was yet another dependency loop.

The solution I came up with was to make both BlackBoard and my custom BT nodes templates. Now these templates are not generic, they use functions from blackboard which is accessing GameWorld members. Both the behavior tree and the black board are instantiated in the new prototype state using class GameWorld. The game world is also instantiated in the same function.

https://pastebin.com/pi6dr5zf

The link above is the PrototypeState::Enter() function. If the ServiceProviders are confusing it is explained in this chapter of a very useful, free online book : http://gameprogrammingpatterns.com/service-locator.html

If you don’t enjoy looking at code, I use the service provider to get pointers to the window for example, but most importantly I initialize the game world, the blackboard and my custom BT. You can see I use the GameWorld class to initiate the black board and the BT.

Now let me draw another sloppy diagram:

DependencyDiagram2.jpg

This looks much cleaner than before, there are no circularity and things only have what they require. There is only one untidy thing, ServiceLocator.h and Graph.h appears twice each. It is OK since I use #pragma once so that they all get compiled only once.

https://en.wikipedia.org/wiki/Pragma_once

I’ll get around to tidying that up later.

Now, I do not know really the pros and cons with making the BT and black board templates that are designed for a particular class. One con is the long BehaviorTree.h file, but when it comes to computer performance and compile time and such I do not know. I get the feeling that some people might object that templates are meant to make more general classes that could handle any data type. If the classes are not generic then why use templates? My low level compile knowledge is not very extensive so I answer that question; why not? It did solve the dependency loop quite efficiently. Anybody who know feel free to tell me pros and cons and perhaps even another suggestion to compare with.

Ok, I need to think about what I do next. I think I should try to get more entities getting steered across the tiles by the BT. I will need more characters sooner or later and I should try to get them going while the BT is still very simple.

I will update as soon as I know any more

Bye bye

Reflections about the research done so far

https://github.com/aigamedev/btsk

There is a book, Game AI Pro, in which one chapter explains and creates the code found in the link above. It is the Behavior Tree Starter Kit (BTSK). The book explains the difference between behavior and actions. Behaviors are the set of logical expressions deciding what the AI does, in other words; what action it takes. An even more formal description is that Behaviors are the nodes in the tree who are parents. The leaf nodes either checks the status of the AI’s surroundings(conditional child) or makes the AI perform some action or task(action child and/or task child).

Among the Behaviors there are different types of specialized classes or data types. Those are the composite, sequence, decorator. All the behaviors can be connected and tweaked to lead towards the desired action in any given time. I am not going to explain this now, I will try to blog about my own implementation and explain as I learn.

There are also the first and the second generation of BTs. First generation are traversing every node from the root and is polling the different conditions among the behaviors. The second generation use event driven traversal which is faster. There are also optimizations in memory storage, instead of allocating the new nodes in a random place you can instead allocate them in a designated place in memory, this is very interesting to me and I need to read more about this. Or perhaps I should implement it just to learn this way of storing data. There are many more and different optimizations, these are just examples which I could think of from the top of my mind after having read the chapter in the book about this BTSK.

I am not sure if I should use the second or first generation. I am not going to actually need the second generation optimizations to begin with so maybe I should start doing a first generation tree and then upgrade it later, but then again why do the slower version if I think I might need to upgrade later? it is more work. besides, I do want to learn the second generation of BTs and I have no deadlines. Yes I think I will do a second generation BT, there are examples in the BTSK of second generation BT optimizations.

I can only read so much, it is time I start practicing. But I am not ready to start programming yet because I need a plan. I am going to describe what I want to do first, depending on what I want perhaps also write a diagram and then I can finally start implementing it.

Next time I will show you what I want my agent to do and how I mean to do them, possibly also why. I will keep it simple.

Bye bye

Planning a BT (Has Nothing To Do with Naar)

I have been away from blogging and making games for almost a year now. I had a lot of things going on at the same time since my education in game design and programming. But I have kept contact with some class mates and a few months ago (January 2017) I was inspired by Force Arena, a fast paced mmo rts – game (Massively Multiplayer Online Real Time Strategy). You play a hero who can move, attack and strategically place cards that will spawn AI-agents that will attack your enemy’s base.

This blog is about what I started doing after having played this game. I have finally done a functional A* search algorithm from scratch using only C++. SFML is used to graphically represent the path generated and to represent the simple agent who uses the A* and walks the path. What I’ve got now is a 20X20 grid containing nodes. Some of the tiles in the grid are walls and not walkable by the agent (black tiles).

AgentIdlingThe white tiles are walkable. (pic above)

 

When one of the tiles are clicked, the pathfinding begins and the agent (blue square) starts walking toward the goal (green tile in pic below). The cyan nodes will turn yellow, red, or blue. Yellow means it is in the open list, the red nodes are in the closed list and the blue nodes represent the actual path.

AgentWalkingPathNow that this is done, a functional A* path finding algorithm, I want to start to give the agent some behavior, and also create new agents. For the first iteration I want two teams, both walking toward the other team’s base. That’s it. I will increase complexity every time I finish a task.

I am going to use a Behavior Tree as opposed to Finite State Machine because first of all I want to have made one. I know there are very useful tools around such as Unreal Engine 4’s Blackboard which is a visual BT, but nope, I am doing this for myself. The other reason is that BTs provide a better overview over the decisions than a state machine – making transitions of agent states  easier to author. So I’ve heard. More of a dynamic feel to it than FSMs.

So what do I want to have in this BT? I skip all the formal names of all the nodes and what not for now because I am at research stage as of now, so I will just type it down. I want the agents to see if their enemy’s base is on a walkable tile. If it is, start the pathfinding algorithm and walk there. When they arrive they will make a note of it. I don’t know, a bool? A message to somewhere? don’t know yet. That’s it for today! I’ll return for an update on my first BT!

 

BTW, If you want to ask something, go ahead!

 

Peace out! (peas out, pees out)