search

Qfusion / qfusion

Source code for cross-platform OpenGL gaming engine
http://qfusion.github.io/qfusion/
331 stars 124 forks source link

Improve AI #307

Closed dnk777 closed 7 years ago

dnk777 commented 8 years ago

I have a plan to significantly improve AI. About 20% or planned changes are made, and progress will depend heavily of my load at work, but current changes are already worth to see. My code is in very early stage, and contains well-known bugs (a memory corruption source of what I did not spot yet), but I cant wait to share progress. The code is in development in my fork.

Done:

Short-term goals:

viciious commented 8 years ago

I tested the branch a couple of months ago. I did experience noticable fps drops on wdm1 even back then so I assumed things have only gotten worse since then.

viciious commented 8 years ago

Note that the longer the branch goes on, the fewer chances it has to ever get merged. There's no physical way I can possibly review 200+ commits with tens of thousands of changed code lines. Not to mention the fact that you seemingly prefer to ignore my comments.

dnk777 commented 8 years ago

It is almost complete, I will commit the last major native code change in a few hours. But there are known minor bugs, so the entire next month the branch will be actively tested for stability, including public tests and some minor changes to conform your requirements will be made.

From the script part I did not touch the bomb script yet (it allows this gametype to run but bots have poor behaviour). The last changes were almost entirely related to support of most CTF:T features from AI side, and players highly rated it. Adding a good bomb support does not require changes in native code (since I have coded a support for generic gametypes with defence/offence spots).

viciious commented 7 years ago

hi @dnk777

Any estimate on when you believe you're done with the changes? Not that I'm particularly fond of some of them (the introduction of "script weapons" is one of them) but I really need to do some filter-branching on master and would like to have this merged ASAP.

dnk777 commented 7 years ago

That branch is frozen, no changes are planned. This means all gametypes have basic support and there should not be any critical bugs (I ran the code under AdrressSantizier and fixed detected bugs). So should be ready for merging.

This however does not mean I consider AI development complete and will abandon the development complete. They give a good illusion of a real match in CTF, CTF:Tactics (thats why I put effort in CTF:T, playing it was funny) but in bomb individual bot weakness is noticeable and very distracting, especially when bot is on his own at the end of round and you have to spectate it. Thats because I did not put much effort in individual bot AI, most of the time was spend on fixing movement, teamplay logic (which is quite solid so will be kept almost as is) and supporting gametype features via scripts.

TL, DR:

1) Individual bot AI should use GOAP as described in http://web.media.mit.edu/~jorkin/gdc2006_orkin_jeff_fear.pdf. The code now as is is a messy FSM where state transitions are spread over it, so modification and tweaking it is a pain, and thus forcing bots to expected behaviour is a quest (for example bots are too easily distracted by enemies in bomb and ignore planting often). Thats how planning code will look like https://gist.github.com/dnk777/f2aa5bd9312bfb101b3b49ab6993121d (the code is in my private sandbox).

2) Old navigation nodes will be reused as anchors for tactical spots for proper positioning in fight, properties of nodes as tactical spots and mutual spots reachability/visibility/other relationship will be precomputed at map loading.

3) These changes will be implemented but 2-3 months later, I have already spent 10x more time than expected and want to take a rest of it.

viciious commented 7 years ago

Well, since there have been no pull requests from you, I'm assuming you would rather prefer to keep your code out of the mainline and maintain it yourself

viciious commented 7 years ago

Also note that now that no longer maintain Warsow, I'm probably going to eventually deprecate all gametypes except for duel, bomb and rekt (which remains unpublished).

dnk777 commented 7 years ago

1) Scripts are modified, so if you need rekt gametype support give the script to me and I will modify it to be able to launch it. 2) I admit that mine code has poor quality and there might be several minor glitches. Thats because I was completely unaware both of AI domain and the engine starting the project. I got a clear vision of what AI needs only when I crafted support for all gametypes. I will address that in a patch later along with a proper support for bot planning, positioning and reasoning via GOAP (which I have already started to implement in a private repo as posted in the gist above; the code base is almost entirely kept but is much cleaner and loosely coupled from the first look than existing). 3) The code and script interface will be documented in the project wiki when I submit the mentioned patch later.

dnk777 commented 7 years ago

I ought to write some kind of report on bot development, since it might seem abandoned, but it is not.

I feel a bit sorry for that I has to diverge my branch a lot (again), but I have an excuse, the introduced features took/are taking significant amout of time to implement and test to ensure they work as indended before I am able to claim they are completed, and they are (sometimes mutually) dependend, so I cannot split feature sets and work separately.

First, the GOAP (Goal Oriented Action Planning) was introduced as a method of implementing bot decision making in well-structured way instead of if-conditions and state primitive variables spread over the code. The GOAP is generally described in the paper above. However mine implementation is very different because they use search from the goal world state to the initial one, and I do the opposite (this makes using procedural conditions natural, and also makes the suggested action sequence way more controllable). Tbh GOAP is a pretty trivial thing once you get it. Also a script interface to the bot planner is added. There is an ability to define goals and actions (sequence of actions satisfy goal) in scripts, and also add script-defined actions to an existing native goal. For example if a player class has a cloaking ability, you can define a SneakCloakedToNavTarget action and tie it to the native PickupItemAction, and then bots would use it to sneak into a flagroom cloaked, or just sneak to an item/tactical spot to prevent being spotted and damaged, and it does not require hardcoding custom gametype features in native code.

Then I had to add an evolution algorithms support for action/goal weights. First tests of GOAP results often shown awkward results. There were lots of numeric constants in the code that affect bot behaviour, modifying each of these constants might change things a lot, and manual tweaking is just counter-productive when a substantial count of these constants is reached. All constants that tied to GOAP goals/actions are converted to config vars and hierarchical groups of such vars, and are serialized to a text format. A basic support for randomizing config weights for bots at start based on a previous best weight config and selecting new best weight config based on a match results is added. There is an ability to override randomization/selection of best config rules in scripts, and add vars and var groups in scripts for script-defined actions that are serialized along with the native part of weight config. Separated weight configs for each gametype and even each map are supported via native code. There is also a possibility to fine-grain control bot weight configs in scripts, for example it is possible to assign class-specific weight config to the bot when its player class gets changed.

Bot evolution feature has proven to be working, there were public playtests in January that included 40 (!) bots playing on a single map (wdm7) in ffa mode, and is was noticeable that best bots in selection start play much less awkward after 2-3 days of evolution. IIRC Q3A bots use a similar feature (not for final releases but in development to get a good weight config).

Frankly even after implementation of these two features results were not satisfiable for me. Still present bot movement troubles were hiding improvement in decision making. Then i noticed that Q3 bots predict movement results for several frames ahead in runtime. I known the existence of such functionality in AAS code base but thought it is used only in bspc. From what i read UT games predict bot movement ahead too up to several dozens of frames ahead. I have however introduced a much more advanced system to fix the bot movement ffs.

In Q3A, a movement action gets selected for the current game frame, ucmd/angles are produced and then a movement gets predicted for several frames ahead with a fixed input defined on the first frame, and results of the prediction are checked in the current game frame. This gets repeated on next game frame. I modify ucmd/angles according to the prediction frame state on each frame selecting a suitable movement action, use variable timestep and caches of helper tests for each frame. If a movement action sequence application leads to a failure in the predicted state, the prediction stack can be rolled back, and action can be restarted with different params or disabled for further planning. Prediction results for frames are saved and might be used in next game frames until a misprediction error accumulates, and this allows to mitigate possible performance issues from this approach.

The movement prediction feature is still in development, tweaking and testing and cannot be considered ready for public testing but already produces solid results. Bots (almost) never miss item pickups, bump into walls unintentionally and go into undesired areas, all of this mostly keeping bunny-hopping. I would stay with basic movement for this branch to avoid it further growth (for example current bots in master aggressively use rocketjump shortcuts, and I have rocketjump movement prediction code that simulates knockback, but I keep this code private without intentions to include in the branch because it would take lots of time to integrate and test it).

I am going to add only critical or very, very important fixes in my branch (I can suggest lots of improvements but they are to be submitted later in separate branches), but I have to spend a month of tweaking/testing the code, especially for all gametypes, to ensure it works.

viciious commented 7 years ago

I've been following your progress on the GOAP branch, nice to see you're still working on it. Although I can see how troublesome the eventual merge is probably going to be.

It'd be nice if the new AI code was reusable for monster intelligence, not just bots alone.

dnk777 commented 7 years ago

Poor movement has been the bane of the AI since I have started working on bots. Luckily there is a solution that have started producing solid results, the bot movement prediction system. This system allows to test all applicable movement actions in a sandbox and save the path of a successfully applied action for reusing in future frames. Its so powerful so I had a surprise when it rejected almost all bunnying attempts produced by a code that was similar to the existing code in the master branch. Writing movement actions that pass all prediction tests is not an easy task and requires lots of tweaking and ideas testing. Each commit related to the movement system since March has been updated and rebased not less than 20-30 times (and still might be). I tried to avoid adding extra commits in the branch but I had to do it for some important things (and also I rather add a fix commit now than update and rebase an existing one that is dated 1-2 month ago, I want to avoid rebasing a long commits chain due to it being quite error-prone).

Here is the video of bot movement prediction system in the current state. A path built for an action that can be applied to the current movement state is shown. The first part of the demo was recorded using notarget cheat, and also timescale is a bit lower than the normal.

http://webmshare.com/VJNOj

I did not try to hide any glitches that appear. There is still a known bug very noticeable on the video. A misprediction occurs way too often and the entire predicted path gets invalidated leading to losing speed/switching to a dummy movement, and the bot movement is rather poor due to it. Ideally bot movement prediction system should not get activated again until the bot origin reaches the end of a predicted path. I need to investigate a source of the bug since I have tried to visualize the origin delta error and the error pattern looks regular, like a position with +/-16 millis offset of an expected origin. Its probably a some issue related to predicted action timestamps. Also switching to a dummy, non-predicted movement is noticeable in the beginning of the video near the A-spot UH (no path is shown), and it leads to weird movement especially in the mentioned area. This kind of movement should be avoided, but I still did not manage to write actions that are applicable (pass all prediction tests) for all situations.

There are already great results in such areas as:

1) Crouchsliding, its noticeable at 0:41 on the video, its very cool to see bots doing it. 2) The combat movement that is purely amazing, they have mad dodging, and also notice it is predicted (as almost any other kind of movement) and should never lead to falling into pits/lava/losing a tactical position. I hope other movement actions would have the same quality as the combat one.

My plans consist of fixing the mentioned misprediction bug, adding some minor features (like forcing backward movement switching from combat to running to always face an enemy) that totally are estimated in a minor amount of code (about 200-250 loc totally) and testing for critical bugs and gametype compatibility. I still need an extra month to finish it.

dnk777 commented 7 years ago

It'd be nice if the new AI code was reusable for monster intelligence, not just bots alone.

I have no idea how monster code would look like if somebody decides to implement one, but all 3 major features introduced in the branch (GOAP / genetic weigths optimizer / movement prediction system) are very generalizable with relatively low effort (and other bot code like aiming, squad formation, etc too). For example, arbitrary script attachments to the GOAP logical world state, scripted GOAP goals and actions are already allowed.

On merging... rebasing it over master is very painful (mainly due to uncrustify applied right after the branches have diverged), but merge with master without rebasing is pretty straightforward (especially if I run uncrustify as a last commit in my branch).

dnk777 commented 7 years ago

Here is the list of issues I plan to continue working on and sumbit series of tiny patches for each one:

June:

July:

Later:

dnk777 commented 7 years ago

Add PMove() flags to skip some expensive collision computations when PMove() is used for bot movement prediction and these computations are redundant for a given context.

To explain this a bit: on each movement prediction step a coarse environment test might be performed. If a predicted origin is inside bounds of a huge AAS area, its very cheap. In worst case, a single box trace test is performed. If this coarse test succeeds, there is no need for further obstacle checking. Results are shown on this video http://webmshare.com/m8OOG. If this coarse test has not detected any obstacles (green lines drawn from tested box mins to maxs) and the bot is above ground, PMove() should skip very expensive "stepmove/slidemove" collision computations. I has not added PMove() hint flags in this branch trying to keep all introduced changes inside the /ai subdirectory. If these hints are added, they allow to significantly reduce CPU load or/and allow better quality of bot movement action checks.

Here are some issues I forgot to add in the list above:

dnk777 commented 7 years ago

Also I have rewritten the first commit that introduces the bot movement prediction system to skip all collision tests against entities in PMove() call (the code commits are self-explanatory). I have tested 32 bots playing FFA on a listen server run on 3 GHz Intel and got these results: 130-170 FPS on wbomb1, 150-200 FPS on wdm8. (Note: I have used the mine proposed CM improvements). If PMove() hints are added later, there should be a significant performance boost too.

@@ -384,6 +384,12 @@ static void Intercepted_PMoveTouchTriggers(pmove_t *pm, vec3_t previous_origin)
     game.edicts[pm->playerState->playerNum + 1].ai->botRef->OnInterceptedPMoveTouchTriggers(pm, previous_origin);
 }

+static void Intercepted_Trace( trace_t *t, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end,
+                               int ignore, int contentmask, int timeDelta )
+{
+    trap_CM_TransformedBoxTrace(t, start, end, mins, maxs, nullptr, contentmask, nullptr, nullptr);
+}
+
 void BotMovementPredictionContext::OnInterceptedPredictedEvent(int ev, int parm)
 {
     switch (ev)
@@ -1023,8 +1029,21 @@ void BotMovementPredictionContext::NextMovementStep()

     this->frameEvents.Clear();

+    // We currently test collisions only against a solid world on each movement step and the corresponding PMove() call.
+    // Touching trigger entities is handled by Intercepted_PMoveTouchTriggers(), also we use AAS sampling for it.
+    // Actions that involve touching trigger entities currently are never predicted ahead.
+    // If an action really needs to test against entities, a corresponding prediction step flag
+    // should be added and this interception of the module_Trace() should be skipped if the flag is set.
+
+    // Save the G_GS_Trace() pointer
+    auto oldModuleTrace = module_Trace;
+    module_Trace = Intercepted_Trace;
+
     Pmove(&pm);

+    // Restore the G_GS_Trace() pointer
+    module_Trace = oldModuleTrace;
+
     // Update the entity physics state that is going to be used in the next prediction frame
     entityPhysicsState->UpdateFromPMove(&pm);
     // Update the entire movement state that is going to be used in the next prediction frame
dnk777 commented 7 years ago

The following contents https://gist.github.com/dnk777/063785d84087a446623ce69bbfbd5087 is expected to be in /ai game filesystem subdirectory under the generic.weights name. It is a result of 70+ hours of bot evolution in FFA mode. Otherwise the currently hardcoded bot behaviour might seem weird (and really is).

These weights are of course not final, and would be threated differently when I tweak the bot logic. For example, there is a separate ReactToThreatGoal (it gets activated when a bot gets a damage from an attacker). I have added a concept of "points keep in fov" as one of the last commits in this branch. This point is set to an enemy origin/just lost out of sight enemy origin. A bot might invert his movement (move backwards) trying to keep this point in fov if the point is present and it is necessary. I have an idea of setting this point to a possible threat source, and thus weights of the separate ReactToThreat goal should be lower (but this goal is still needed in some cases).

Also weights for objective-based team gametypes should be assigned dynamically for defenders/attackers/different player classes when a bot changes its role/class. It is also remains a thing to be done in future.

viciious commented 7 years ago

The following contents https://gist.github.com/dnk777/063785d84087a446623ce69bbfbd5087 is expected to be in /ai game filesystem subdirectory under the generic.weights name. It is a result of 70+ hours of bot evolution in FFA mode. Otherwise the currently hardcoded bot behaviour might seem weird (and really is).

Please submit a pull request here: https://github.com/Qfusion/rapid/

I'm closing this issue as it's become too generic and huge to remain comprehensible. Please restrain yourself to smaller tasks further on.