Tweaking Pathfinding

[synopia]

Okay, here is a short update:

Code compiles in multiplayer/restructure branch and all tests are green again. I did not started Terasology with the mod, probably nothing works

Maze: In the old code there was a maze generator wrapped into a chunk generator. I think, its completely the wrong place - Mazes should be placeable anywhere in the world, maybe at runtime. So I will restructure that code into a tool (for example, after placing two blocks in the world, a maze is generated between those blocks). Code should be accessible for other modules.

Pathfinder TestWorldGen: For testing the pathfinder, there is a pathfinder world generator. It will generate a world consisting of levels with 16x16 block rooms and a stair in the middle. This will stay in code. Its also used in some tests.

Refactoring pathfinder: There are some flaws, that should be fixed asap. This are primarily API design (pathfinding should be simple to use for every mod). Until this is more or less stable, I wont change any core code (@DizzyDragon suggestion will be realized after this - I think (hope) this is a minor change).

Multiplayer: Here I first need to play around to get a final idea, how everything should work. Maybe paths should become entities, so that they can be shared between server and client easily.

Next steps: My first goal is to get a new tool, that marks any block and makes a creature (with new models from glasz) go there. I suppose, some code 'stubs' are required, to get this working (simple minions, marking a block, walking creatures, etc). I will implement those stubs, as I need them. Of course, they could and should be removed and replaced by enhanced code later.

 

[Immortius]

IMO, there's no particular reason why paths should even exist for the client - they're only used by the AI, and the "brain" of the AI should only exist on the server.

 

[synopia]

Made some progress:

Got glasz new models working ingame. Whatever he changed, the models are working now. If you want to include those models into your module, look into my asset folder.

Speaking of assets, probably the most important is the prefab for red pawn. Here you can also see two new components introduced by the pathfinding module:
MinionPath - a component with one property: target. If set to a world coordinate, the path from current position to target is calculated in background and the entity starts moving along the best found path. Once finished an event is sent back to the entity.
JobMinion - minions with this component will take part at the global coordination of jobs and minions. The basic jobs are "moving to a block", "use item at block position" and "attack item/entity at block position". More complex jobs will be constructed using those basic jobs.

Everything is in very early stage and I have some more or less big refactorings in mind

Also, every system is marked with RegisterMode=ALWAYS, which means I did not even tried to start multiplayer

Question:
Would it be problematic if components are added and removed to several entities (block entites and minions) on regular basis? Currently, when a minion is assigned to a job, it gets a new component added at runtime. When the minion finished the job, the component is removed.

 

[Cervator]

Woo progress!

Components are meant to be removed/added at runtime to affect behavior, so that's fine - especially if it is only on occasion like at the completion of a job. Maybe something that added/removed at every single tick would be kinda bad

 

[Immortius]

There shouldn't be any issue with adding and removing components in general - it might make the entity eligable for replication (which might need to be worked on in the multiplayer implementation as some components won't need to be replicated). At any rate it is something the engine should able to handle.

Note that components added to blocks won't stick unless specifically marked, due to block entities being temporary by default.

 

[synopia]

So, weekend update:

1. Added knight, queen and rook to LightAndShadowResource. Have a look into the attached screenshot.
2. Fixed a lot of bugs and issues.
3. Tuned the systems (now there is move system (to make minions move one block) and path system (to make minions move along a path). Both systems fire events, in case they are stuck or cant find a path (anymore).
4. Experimented with several implementations of a simple job scheduler. For now, you can assign jobs (remove block, add block and walk) to any block. The scheduler figures out, where minions have to walk to, in order to operate on the job. All possible jobs are then collected into a huge list (job board). Last step is to match possible jobs to idle minions (with some kind of scores, that depends on path length, job priorities and the minion itself).

Point 4 is work in progress and not finished. There are many options and implementation details to consider, so it still might take some time to get it stable.

 

[Cervator]

Awesome

It looks like the models could still be scaled slightly more realistically, but I figure that's fairly easy. Knight and Rook look tiny

 

[glasz]

My bad, i kind of overlooked the scaling part

 

[Cervator]

Small integration note: with some refactoring work by Josharias for the Core module some changes affected Pathfinding (also LASR, and probably others). Since it is my favorite testing target in Jenkins I went ahead and applied some minimal fixes just to get compilation and testing working. It still doesn't actually run due to some sandboxing issues

synopia - hope you don't mind! Might need to do a gradlew cleanIdea idea (adds the Core dependency - although the exact way that works will likely change again soon)

Let me know if any unit testing issues remain. Currently works for me locally in IntelliJ, via gradlew check, and in Jenkins

 

[Mike Kienenberger]

I took a look at behavior and Pathfinding, although I had issues with the Behavior Editor rendering:

https://gist.github.com/mkienenb/8498464

Here are some first thoughts. None of this so far is on how it works so much as how it is structured.

1) Pathfinding as a module is almost useable without NUI or your engine mods.

The only compile-time dependencies I hit were
-- the eclipse .classpath generated seemed to have a dependency on L&SResources even though LASR has no java code. Not sure if this also happens in other IntelliJ.

-- The various *Node classes. This is the tie-in between the systems in Pathfinding and behavior, but I wonder if there might be a better place to have these since they are not actually needed to use Pathfinding/Jobs code. Maybe a moot point once Behavior is in the engine, but these are obviously consumers of the Pathfinding system and not the providers of the pathfinding system, or at least I would think that they should be. Possibly they need to be wrappers around non-BT-specific versions of the same code.

2) Behavior is integrated into NUI

BT seems tightly integrated with NUI. BehaviorTreeData only contains three fields, and two of them are based on the NUI RenderableNode. The type used where RenderableNode currently is should be an interface with no NUI references rather than a NUI implementation. I'm not sure how hard this will be in practice.

Also, there are references to NUI property annotations that probably should be rewritten in a way that there's no direct dependency on NUI. It's fine to annotate a field with some kind of indicator of what GUI element should be used, but Property and Textfield aren't just marking a field, they are defining the NUI implementation. I'm a novice when it comes to annotations, but I'm pretty sure this is feasible. Again, it's probably a matter of using an interface instead of an implementation.

I spent a few hours, and this is what I came up with as a way to decrease the dependencies. I don't know if you want to use this:

https://github.com/mkienenb/Terasology/tree/remove-nui-dependencies

I don't now if it works, although it does compile (except for the tests -- it's too late here for me to take a stab at those as well).

The basic idea was to make Node into an interface, and make RenderableNode implement that directly.

I tried a few different approaches at first, so this is not perfectly implemented. The assets part still needs a bit more work, although I started at it with a now-obsolete factory class. BehaviorNodeComponent should really be BehaviorNodeRendererComponent or some-such. And it should be moved into NUI. And the BehaviorNodeFactory should be rewritten so we don't access it directly (as an interface) with the implementaion of that factory in the NUI directory. You might consider having Nodes as entities instead of POJOs. Then you could attach the NUI specific stuff as a component on asset loading, and have it hidden until the editor needed it. That's probably the best way. You probably could also leverage that setup to make saving/loading nodes more natural.

But My Thinking is becoming a bit blurry now. it's 30 minutes after midnight here, so I need to stop here for now, which is why the last couple of items above are not as clean as they should be. and there may be some wrong thinking involved in my last few lines of commentary.

 

[synopia]

Hey, first thanks for the feedback.

1) My suggestion was, to make BT nodes something like a API for modules for AI stuff. So, mods should have their "normal" code (in this case the pathfinding algorithm) and several behavior nodes, that are used by the BT. I dont want another module for all the nodes, or something.
The LASR dependency is, because for testing I use the L&S models. This should be removed, of course.

2) It took a loong time, to decide how to actually implement the tree and the nodes. I decided to decouple rendering from interpreting the behavior tree. So there are in fact two trees (RenderableNode and Node).

Node is an interface for all nodes. Its designed in a way that nodes without children or any other required data, will take no memory at all (except the node class instance of course). There are no empty children lists or something like that. You will find a small inheritance tree for the nodes (decorator, composite, etc). New nodes should always be implemented using Node, Decorator or Composite, only. No render specific stuff here. A tree of such nodes is everything needed to interpret the tree.

RenderableNode is a widget, which renders a node. RenderableNode is able to render all types of nodes using a BehaviorNodeComponent (Notice, the palette is a list of BehaviorNodeComponents). There is no second inheritance tree. Also, RenderableNode keeps track of currently connected childs and there connection positions to draw links (this does the class Port).

The property annotations are part of nui (at least I think so). They are only required by the editor. All annotated fields are visible in the property editor (part of BT editor), where you can setup nodes and manipulating the values of any Component, that is assigned to the current minion.

The asset loading stuff is done in analogy to other assets (thats why there is an Asset and AssetData). Dont know exactly why, but doesnt matter - this thing currently can load (and write to some extend) both parts of a behavior tree (nodes and renderables). So this is dependent of the editor/nui and needs some rework to be merged without nui. Yesterday I was also wondering, if we need to save the renderables at all - because I use an automatic treelayout, so no need to store actual positions of the renderable nodes.

3) Nodes: Entity vs Pojo

Good question. Again, took me some time + experiments to decide, which way to go. But I have no strong arguments for the way ive chosen Its more a feeling, that the nodes in a behavior tree have nothing to do with entities in terasology. They are more like a Java method. Another consideration is the memory footprint. Entities are not that cheap (as a pojo without any dependencies) and the behavior trees may become really big.

Now I look into you branch and think about your suggestions

 

[synopia]

Ok, I removed all nui related stuff in this branch: https://github.com/synopia/Terasology/tree/behavior_no_nui

But since, Immortius merged nui into develop already, I tidy up some code and pull requested the behavior branch maybe we should discuss code related issues there.

 

[Mike Kienenberger]

Sorry -- I only have a few moments this morning, so I don't have time to read what you wrote yet, but I wanted to write this out before I forgot.

But I woke up sure that everything is flipped on its head, and the tree needs to be a tree of entities (currently with a generic TreeNodeComponent, a BehaviorLogic component, and a BehaviorLogicTreeNodeRenderingComponent).

Any time we see a delegation pattern like RenderableNode/Node was doing, it's probably an indication that it should be flipped into an Entity pattern instead.

More info later when I have time.

 

[synopia]

I finally managed to get Theta* running. With this modification a path may contain gaps between two points, if there is a direct line of sight (better: line of walk) between the points.
As an effect of this, the MoveAlongPath node does not move the minion in single step mode through the path, anymore. This was by the way a major issue with the current movement code - the distance between to adjacent blocks was just too small let the minion gain speed.

Now this works much better, because the gaps in the paths are used to accelerate. However there is still some investigation needed here to fine tune everything.

Another topic is the job stuff, I mentioned before somewhere else. Still needs a better name. Initially this was thought as a throw away prototype, to make testing behavior tree and pathfinding easier. But as I tried to get a AttackNode working, I noticed I may reuse the job system.

The job system (aka JobBoard) maintains a list of open jobs (actually, it maintains a list for each job type). Jobs are assigned to entities using a JobTargetComponent. So each job has a target (the block/entity it is assigned to) and a specifiy job type, that defines what to do with the target. Currently there are four types:

• walk to - just walk to the block (on top of it).
• build block - go to either side of the target air block and build a block
• remove block - go to either side of the target ground block and remove it
• attack - go to target enemy minion and deal damage (which is not working right now )

Modules can implement such jobs and register them, so they can be used in behavior nodes. For now, there are two important behavior nodes for jobs:

• FindJob - Asks the JobBoard for a job. Can have filters, like type of or distance to job. Once a job is found, it is claimed by the actor and removed from the open list of jobs. As long as the actor has not reached the jobs target, this node's child is run.
• FinishJob - Do the work at the target to get the job done. This may take some time, depending on the job type.

With this system, the code for the fighting minions is just one Job, which deals damage to the target (however this is implemented). Everything else (moving to target, playing sound effects, draw blood, ..) is done by other nodes. The complex things like finding nearest enemy or the best order to run jobs is delegated to the JobBoard.

Still so much to do

 

[Cervator]

All the related systems are getting sort of confusing for me (naming/function related), I must admit. I think we need a diagram for great justice!

I think I mentioned pondering how the Tasks repo (meant for "quest" type scope - like "Go forth and establish a new colony!" would probably be a sizable Task) would break into these jobs. Then jobs break into behavior nodes, I guess. Which themselves can be put into trees (which is a job?)

Either way I suspect a picture will be worth a thousand words

 

[synopia]

So, first version of the picture is ready

https://cacoo.com/diagrams/huo1Fw2Xvwfy6q1N

I am still working on it - any comments appreciated.
Also, its not exactly what currently is implemented. I will refactor some code, to match the picture asap.

Currently I am experimenting with a better system to dispatch jobs to minions. Here a little screenshot

 

[synopia]

Update:

• Refactored several things in Pathfinding module. Now the diagram fits to the code (mostly )
• Renamed Job to Work. Fits much better.
• Greatly improved the WorkBoard. It now uses a hierarchical k-mean clustering algorithm to build zones of work (aka cluster). To search for open work, only distances to nearest cluster are needed. The recalculation of the clusters is done in background, much like it works in the pathfinder.
• In addition of sending an event when a background task finishes, I added the option to use callback interfaces. This way the integration into behavior nodes is much simpler.

With all those improvement I can happily watch my minions build walls and stuff
Still open is the attack node. But I think everything is in place right now, to start on working that

Edit: Some more documentation!