Home » MODDING HQ 1.13 » v1.13 Coding Talk » Tactical AI: architectural redesign
Tactical AI: architectural redesign[message #317276] Wed, 10 April 2013 15:06 Go to next message
feynman

 
Messages:38
Registered:October 2010
Hi,

I'm planning to take the (tactical) AI apart and re-assembling in a modularized way, allowing smaller improvements over time without the necessity of a complete AI re-write, as was proposed several times but never tackled due to lack of developer time. To be clear: I don't plan to improve the AI per se, but rather improve the underlaying software architecture, allowing others to improve it without having to face overwhelming enemy forces of ~40k LOSC (Lines of Spaghetti Code) all at once. Furthermore, this modularization would allow different features to be turned on or off depending on user (ini) settings, map data etc., which has become a very noble development goal regarding 1.13. Before I put a lot of work into this (including a detailed discussion of my ideas), I have some questions.

First of all, the code seems to be a mix of c and c++. And a strange mix indeed: large parts of the c code emulates object orientation, one of the features supported far better by c++. What I mean is this: there are some classes and objects thereof (e.g., SOLDIERTYPE), but they are C-style POD-structs. Functions operating on these objects are not called in the c++-style object.function(), but in the c-style function(object). Apart from not allowing proper data hiding (encapsulation), this is of course fine and merely a question of personal preference and can be considered OO programming with the same right the c++ style can. But then, why use a c++ compiler?

Don't get me wrong, I don't want to point the finger at any one of the fine folks working on this superb project. But what I want to know: is this style intentional, and as such required for further contributions, or are you stuck with it due to the initial release, and would welcome further contributions utilizing a more "advanced" c++ style? Because, frankly, coming up with a good design in the former style is beyond my capabilities.

Second, I have no clue whatsoever about software development on the MS
Re: Tactical AI: architectural redesign[message #317301] Wed, 10 April 2013 22:41 Go to previous messageGo to next message
Flugente

 
Messages:3387
Registered:April 2009
Location: Germany
Hi feynman, welcome to the pit!

That is a noble undertaking indeed. I remember Warmsteel saying he wanted to do sth like that, but its a few months since I last heard from him (http://www.bears-pit.com/board/ubbthreads.php/topics/312771/Re_What_should_the_AI_consider.html#Post312771). Perhaps he has already done sth and you could use that.

Afaik the old code was pure C, and since them, some modders added a bit of C++. It sometimes seems odd, but I guess it'll stay that way - moving everything to 'real' C++ would be a lot of work with no immediate gain. As long as your new code works, you can use C++ however you like (but please, in a way that other people can also understand Smile ).

We use Tortoise SVN, which has everything needed to commit patches, do merges and whatnot. http://www.bears-pit.com/board/ubbthreads.php/topics/56723/Instructions_for_using_SVN.html#Post56723

Committing new code... RoWa21 is the boss for that, he's the one who grants SVN access. You can also send it to me, but RoWa is the proper way.

I believe that in ancient time, the AI was once a beautiful, cleaned up place, until Sirtech themselves started to wreck it. After that, anyone just piled on it. You will find a lot of very special checks throughout the code that capture a specific quest instance - there is no script above that.

As far as mapping goes, Smeagol and Jasmine are the ones currently active with mapping. Also people like Scheinworld, I guess. But note that how mapping code itself works is... not the most 'researched code region'.

feynman
I am a strong believer in continuous delivery and a highly incremental software development process
Very good, as we had quite a lot of people diving into work and then abandon it without leaving their work behind Smile

I do not know what you have planned, but the AI decision making itself can be replaced pretty easily (its mostly the decision-functions for the states). So a good start would be to create an interface, which would then allow to easily switch between different AIs. Trivial, yes, but better than having to revert once some AI fatally screws up Wink

P.S.: Propably not needed, as you seem to already know a bit about the AI, but a good read: http://www.ke.tu-darmstadt.de/lehre/arbeiten/diplom/2008/Ladebeck_Manuel.pdf A diploma thesis on improving the Jagged Alliance 2 AI Smile


Re: Tactical AI: architectural redesign[message #317303] Wed, 10 April 2013 22:53 Go to previous messageGo to next message
DepressivesBrot

 
Messages:3801
Registered:July 2009
I'd also try Hawkeye and wil473 for mapping.
Oh, and get on the IRC if you want to discuss stuff, link is in most people's sigs.

[Updated on: Wed, 10 April 2013 22:54] by Moderator



Re: Tactical AI: architectural redesign[message #317323] Thu, 11 April 2013 16:35 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
Thanks for your replies. A technical detail upfront: the Visual Express Studio thingy 2012 edition didn't produce a usable binary. I had to download the 2008 version, which did the job. Oh well, no new and shiny C++11 features for me - and I was just getting used to them nifty move constructors, variadic templates, perfect forwarding, new auto semantics, lambda expressions...

Quote:
but please, in a way that other people can also understand Smile

No way! It was hard to write, so it should be hard to understand, and impossible to change! Just kidding, I'll try to use "mainstream" c++.

Quote:
We use Tortoise SVN

Huh, I knew about mercurials 'hg patch' (which is compatible to standalone patch), but have never seen 'svn patch'...? Well, no matter. We'll find a way.

Regarding the diploma thesis, yeah, I know that one, and I also read the not-too-old posts here regarding the AI. But they are mainly concerned with features, not structure. So while I tried to make these features and ideas "easily implementable", I don't think I can use any of that work. But I hope to be able to coordinate my efforts with anyone currently (considering) working on the AI before I start coding (and regarding the thesis... I really dislike AI "learning" behavior. It sounds great and all, but quoting from the thesis: "Actually the learning task is quite difficult, because the key to victory in 'Jagged Alliance 2' lies very often in the intelligent use of the environment." Well, duh. In my experience, the only way of getting the computer to perform anything useful at all is to feed it model knowledge. Every learning system I've seen so far was, after an extensive learning phase, still worse - by far - than any half decent non-learning system properly exploiting model knowledge was from day one. AI quality is hard to judge; but there is a reason why ANNs, GAs, SVMs and whatnot are rarely, if ever, used in any area of application where you *can* measure quality objectively, and if they are, the results speak for themselves. But what am I saying, I don't even intend to improve the AI, I solely want to improve its architecture).


OK, as the "formalities" don't seem to be a big problem (i.e. no code sponsoring required but no suitable sponsor available, no overly restrictive coding standards or so. requiring me to go on a two-year bug-hunt before touching anything new etc.), I'm now going to post a first proposal for a new AI architecture. My hope is that we can discuss its pros and cons here, then I will perform the necessary adjustments until enough people are happy; after that, we (well, that's probably somewhat optimistic, let's say I for now...) can perform the appropriate refactoring.


I propose the following:
There shall be two levels of abstraction, one high-level, decision-making side and one low-level implementation side. Plans shall represent what is to be done, while plan implementation shall describe how it is done.

As pointed out by LaValle (who wrote a great book on planning algorithms, which is available free of charge at http://planning.cs.uiuc.edu/booka4.pdf), a plan basically is indiscernible from an algorithm (and, thus, Turing machine). It is of little use to discuss philosophical details here, but surely we can all agree that plans are quite complex; they can be concatenated and may have a hierarchy, allowing (at least!) anything a context-free grammar allows us to construct.

An important feature of the new architecture is extensibility and interchangeability. To provide both, combined with concatenation and sub-planning features, the logical architectural choice for plan representation is the Composite design pattern. I thus propose the following class hierarchy for plan representation (I made an UML diagram, but can't upload it here... where is the 'File Manager'-link advertised in the faq?):


class Plan
{
    private:
        std::deque sub_plans_;
    public:
        virtual void execute(SOLDIERTYPE* pSoldier) {std::for_each(sub_plans_.begin(),
                sub_plans_.end(), [] (Plan* p) {p->execute;})}// Oh right, no λ-expressions without C++11... so when did you say we wanted to migrate?
        virtual void add_sub_plan(Plan* p) {sub_plans_.push_back(p);}
};

class PickupItemPlan: public Plan {...};
class MovementPlan: public Plan {...};
class ExplorationPlan: public Plan {...};


These examples for plan specialization may have a wide variety in complexity; a PickupItemPlan may assume that we already are at the correct location. A MovementPlan may have a target, but has to figure out the best way to this target itself. An ExplorationPlan may have several MovementPlans as sub_plans_, which are executed recursively via MovementPlan::execute - which, in turn, may be executed by its superclass and so forth, which means that it suffices to call the one execute of the "master plan" associated with an object of SOLDIERTYPE; concatenation and hierarchy as well as the differentiation between subclasses of Plan are handled transparently.

Side note: to increase flexibility even further, a visitor (as in Visitor design pattern) could be passed along the execute-call-hierarchy, giving the execution a different flavor for each visitor type. I decided against this, because I believe that it would be over-engineering. But feel free to vote for it anyways Wink

This architecture allows a new type of Plan to be easily defined, and keeps a "high level representation" (namely the objects of the newly defined type) and its implementation (i.e., the execute() method) local (w.r.t. the source code), which alone should be a large improvement over the existing code. Apart from allowing new types of "plan components" it also allows to provide a different implementation for existing components, e.g. a MovementPlan could be specialized into a LightAvoidingMovementPlan, a LightSeekingMovementPlan, and a LightIgnoringMovementPlan. This also is beneficial for easy experimentation on new implementations (have some NPCs use another implementation than the rest, and see who survives longer...).

That is the lower part of the AI, representing implementation. The upper part, whose task is to generate a hierarchy of Plan objects for each :SOLDIERTYPE, also should be rather flexible (after all, this is the place where we decide if LightSeekingMovementPlan or PickupItemPlan is to be instantiated, in short, this is the real "brain" part). To this end, the Abstract Factory pattern was chosen.

class PlanFactory
{
    private:
    public:
        virtual Plan* generate_plan(const SOLDIERTYPE* pSoldier) = 0;
        virtual void update_plan(const SOLDIERTYPE* pSoldier, Plan* plan_to_update) = 0;
};

class EliteSniperPlanFactory : public PlanFactory
{
    private:
    public:
        virtual Plan* generate_plan(const SOLDIERTYPE* pSoldier)
        {
            Plan* result = new Plan(pSoldier);
            result->add_sub_plan(new SeekCoverPlan(pSoldier));
            result->add_sub_plan(new AimAtDirectionPlan(pSoldier));
            result->add_sub_plan(new DontMovePlan(pSoldier)); // Hey, I've got no clue about military strategy, but my snipers don't run at the nearest enemy they hear...
            return result;
        }
...
};

class CivilianPlanFactory: public PlanFactory {...};


class ScriptingPlanFactory: public PlanFactory
{
        virtual Plan* generate_plan(const SOLDIERTYPE* pSoldier)
        {
            Plan* result = new Plan(pSoldier);
            while(ReadScript(pSoldier->script_filename))
                result->add_sub_plan(script.step()); // well, that's a little oversimplified, I know, but you get the idea.
            return result;
        }
};

Side note: It is obvious that a concrete factory implementation needs to know the available Plan subclasses and their behavior. So yes, the concrete factories depend heavily on the available plans, and adding a new Plan subtype also requires the adaption of at least one concrete factory in order to be used. I'm sorry for this, but its the best I did come up with (well, apart from a really freaky interface allowing a generic and high-level description of what a new Plan subtype does. But again, I'd consider this to be over-engineering.) So the abstract factory has a plan generation and a plan update interface:

Waitaminute, why the abstract factory pattern if we must know which concrete factory to call?! We don't want to use the EliteSniperPlanFactory for civilians... well, we define a "global" vector of abstract factories:

// in some global structure:
std::vector planners_; // where would that be, exactly? Haven't looked much outside the AI code yet...
// initialization:
planners_[0] = new /* ConcretePlanFactory defined by ini_file_planner_for_type_0_plans; I won't bore you with impl detail... */
planners_[1] = new ...
...


This leaves the decision which planner in said vector is to be used for a given NPC. I am not sure regarding this yet. Probably each NPC can get a variable, providing the proper index? Alternatively, the indices represent a pre-defined "type" (e.g., civilians get index 0, "special" NPCs like the Queen index 1, soldiers with sniper rifle index 2 and so on). Both versions have their benefits and drawbacks, but again I think providing the flexibility to allow both (i.e., an "Abstract Factory Abstract Factory", deciding about the "real" Abstract Factory instantiation) would be over-engineering. Currently, I'm in favor of the "every NPC gets its own index" variant, as we can provide defaults emulating the second variant and leave more flexibility to mappers, modders & tinkerers. (This is one of the points I kindly ask for your input. Can an enemy flag, which AI to use, easily be added to both the SOLDIERTYPE ds and the editor(s)? Would it be welcomed by the ones stuck with defining it?)

Now on to plan execution. As we all know, no plan survives the first battle intact. Before discussing plan updates, another side note. I believe that this train of thought ("fast" plan updates are important) lead the original developers to a very, very ill-advised design decision, resulting in the very first non-concurrent system I've seen that can actually produce a deadlock (shudder). I do understand the intention: if we plan to go 100m north, but see an enemy after 10m, we interrupt our plan and find a new one. And NPCs that already have executed their plan for the turn also should plan anew. I really do get that. But the answer is not so simple. If we want to simulate concurrency - i.e., NPCs acting "simultaneously" within one turn - this is a task of its own that cannot be built into the plan generation itself without messing things up for good (this is also the reason that I do no longer believe that the original AI behavior can be preserved completely; we need to change the AI calling interface, its very structure is deeply flawed).

At this time I have no definitive answer regarding the plan update/execution "life cycle", so here are some thoughts. I think that in RT mode, plans should be only updated after they are completely executed. In TB mode, plans need to be updated every turn, that much is obvious. And I really would like to see enemies running towards the panic button to stop and shoot me if they see me, so yeah, plans require updates in between turns, too. The Plan::execute()-method could request a plan update through the appropriate plan factory (care has to be taken, though, the resulting call graphs can become ugly really fast leading to a similar f*ck, err, lock-up as the current code; but I'll find a solution). The plan structure would allow to "inject" a "shoot at merc" plan-component into the existing plan "press panic button" without loosing the "real" objective (of course, we most likely never get to press the button if we engage a merc...). I think that is the way to go, but as I said, I'm not really sure yet.

Regarding concurrency, I suggest to execute realizations in a *fixed* and pre-defined number of "smaller pieces". Each NPC gets, say, 10 time slots in each turn, and then realizations are executed Round-Robin style. This would allow patrols to stay in formation in TB mode (I really would like to see multiple-enemy patrols on AIMNAS/bigmaps) and engage the player as a group. As usual when using Round Robin scheduling, smaller timeslots are "better", but have a bigger overhead. So the player decides just "how concurrent" the enemy shall behave. Of course, some actions require more than 1/10th of the available APs, so they use up more than they "should", but that is OK; the NPC will get scheduled once the turn is "progressed" far enough, i.e, each soldier "not resting" has only so-and-so many APs left.


What are benefits and drawbacks of the proposed system?
As already discussed, new "Plan components" as well as plan factories, defining the "how to do it" and "what to do", respectively, can be added quite easily. If one does not like a new AI factory, one can exchange it with another, allowing a "fun to play", "military simulation", "extra-hard and omniscient" etc. set of AI factories - provided, of course, someone gets around to implement them. But the architecture suggested should encourage experimentation and smaller contributions. On the content designer side, it would be possible to let a groups of NPCs by a controlled by a specified type of AI factory, e.g. "sniper AI", "patrol AI", "civilian AI" or even "scripted AI" as explored above. The concrete AI factories need not be stateless objects; the can (and, at least in some cases, should) "remember" what was planned for another NPC, allowing e.g. a patrol AI factory to discern between the leader of a patrol and the soldiers following him in their position within a given formation, and allow sharing of information (e.g. enemy positions, places of the other soldiers within the formation, or even a whiteboard AI, as was first used in The Sims, IIRC, where each entity writes demands and resources it can provide on an imaginary whiteboard, which are then paired up; e.g. leader writes 'require suppression', saw guy writes 'can provide suppression', you get the idea) within such a formation - avoiding cluttering, employing team tactics and so on. The "not stateless"-aspect of the factories also allows artificial neural networks, fuzzy logic etc. to be utilized (although I have to admit that I don't see much merit in such systems; but then again, I'm no AI expert - but I did mention that earlier, didn't I...), and the one implementing it does *not* require extensive knowledge regarding ja2-specific implementation detail. If a plan component does what it says, it suffices to instantiate it; to use PickupItemPlan, I need not to know how 'hands' work. This separates the knowledge requirements (AI expert, JA2 expert) of working on either part of the AI, which should further encourage contributions.

I believe that the main drawback is that it requires a massive change in game structure, which is somewhat contradictory to my previous statement of continuous delivery and SCRUM tactics (I still intend to use them, but the scale will be much bigger). But the system is messed up good, and simply splitting a function here and renaming a variable there won't cut it. Best thing IMHO would be to make it a (at least) two-man job from the beginning. Any volunteers? Furthermore, it most likely won't allow to preserve the current AI behavior fully, I suspect we will see some regressions in the first version(s). That's the cost of major refactoring, always was, always will be...


Well, that's it from me, your turn... questions, improvements, and reasons why it can't be done or is a Bad Idea are all equally welcome.

Cheers!

PS
Flugente, I've seen the svn logs. Please do remember to get some sleep now and then! Razz
And many thanks for the great contributions you made lately.
Re: Tactical AI: architectural redesign[message #317337] Thu, 11 April 2013 21:48 Go to previous messageGo to next message
Flugente

 
Messages:3387
Registered:April 2009
Location: Germany
I don't think we'll migrate to C++ 11 any time soon, considering it would require effort for every developer (and it wasn't needed until now).

Yeah, the diploma thesis is mostly an introduction to 'our' AI. Though one thing I'd like to have later on is to test different AIs against each other (enemies use old AI, militias use new one, spawn two equally outfitted teams on testmaps and see what happens). Imho it would be very good to have the AI to be switchable for that regard. This will be needed anyway, I see no way the community would accept a sudden 'break' in the entire AI in which the old AI is completely irreccoverable deactivated (for a non-coder) without extensive public testing over a long time. Search in ancient threads for 'A*-pathing' to learn why.

I do like your idea of plans and planfactories. The idea of an higher planner that coordinates multiple soldiers hasn't been tried yet (even actions that seem like they are planned, like multiple flanking, aren't).

Adding new variables (AI flagmask) to SOLDIERTYPE is relatively easy. Something similar (on a much smaller scale, and not really clean) already happens - in the editor, soldiers can be defined to have static/sniper/seek&destroy/etc. - behaviour.

Applying a 'preset' behaviour is good, though it must be easily interchangable ingame (we don't want to update old soldier placements AI data in maps, later exes might give us more behaviours to choose from) and even in combat itself (factions can change behaviour depending on player actions & quests). Imho at some point the game has to decide which plans are valid for a soldier (depending on teams, items, day/night, ...) and update those.

Why not reeavaluate plan execution as it is currently done? The problem with 'reevaluation slots' is that a this leads to subotpimal gaps - the AI reacts to late, or never, etc.. Why not adapt? It can be reasonable to make hundreds of decisions in a single turn. Basically, the AI should follow its plan. If something noteworthy happens (we see a new enemy, for instance), it asks the Plan's 'checkevent(...)'- function. This function would decide - based on event an current plan - wether to continue with the plan, or to use a new plan.

As an example, if the AI has the plan 'run 100m north', and it would see a merc popping up, it would decide to stop running and start shooting. If the event was 'I am shot at, but not hit', it might decide to continue running. These checks could occur at the current decision-making routine.

Plans would also give the AI memory (which it currently lacks). Like it Smile

As should be obvious by now, I am interested in this, so do count me as potential volunteer. Though other unreleased features have a higher priority for me right now. :secret:

Edit: Also, the AI in RT is the same as in TB (as demonstrated here: http://www.bears-pit.com/board/ubbthreads.php/topics/316141/Hideous_bug_or_awesome_feature.html#Post316141). Rarely useful, but worth keeping if possible.

[Updated on: Thu, 11 April 2013 22:07] by Moderator



Re: Tactical AI: architectural redesign[message #317338] Thu, 11 April 2013 22:31 Go to previous messageGo to next message
CapnJack

 
Messages:58
Registered:June 2012
It's nice to see someone take the time to explain some better approaches to the AI as it stands. This is all, of course, out of my realm of experience with modifying the game. Some really good discussion on legitimate ways to improve the AI is definitely needed to spice up engagements in-game (well, and then the implementation haha).

I liked the sound of the whiteboard idea you had where there is maybe a platoon leader with the grandmaster plan handling overall strategy and several squads (possibly specialized) with squadleaders that are controlled/directed somewhat by the platoon leader through the whiteboard but give orders to their squad members. This kind of idea might be too indirect though and possibly slow or difficult to implement, I'm no AI coder. You would also have to account for circumstances where the command structure might need to be disobeyed either at the squad or soldier level. Then accounting for what should happen if the platoon leader is killed.

I also know that in the sims the AI would often do annoying things you didn't want them to do or didn't make sense-causing chaos (they still need management, after all, but this may be more of a game mechanic). Not that current JA2 AI isn't chaotic as is. I suppose unwanted or nonsensical behavior could be worked out through development iteration, especially if it is cleaner and simpler to work on the AI code.

It would be great if the AI could be externalized to a scripting language like python or lua but this is probably a pipe dream and far off at least until the basic AI system structure is worked out to a useable state.
Re: Tactical AI: architectural redesign[message #317347] Thu, 11 April 2013 23:43 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
Quote:
Though one thing I'd like to have later on is to test different AIs against each other

With the new architecture, that would be trivial (it is one of the main design goals to make the AI easily interchangable). In fact, if splitting the AI is performed as I suggested (CivilianPlanFactory and so on), it would be the general case to have multiple AIs in the game simultaneously.

Quote:
Applying a 'preset' behaviour is good, though it must be easily interchangable ingame

No problem, an integer index would serve the purpose just fine. One possible "end result" would be a new set of options in the ja2_options.ini file like
AI_INDEX_1 = CIVILIAN_AI_1 // scared people
AI_INDEX_2 = CIVILIAN_AI_2 // not so scared people taking guns from fallen enemies
...
Now s.o. doesn't like civilians taking guns, he just sets
AI_INDEX_1 = CIVILIAN_AI_1
AI_INDEX_2 = CIVILIAN_AI_1 # same AI as AI_INDEX_1
and they all behave the same. Now a strenuous coder develops a new civilian ai, we can use the old maps with it:
AI_INDEX_2 = CIVILIAN_AI_3
Or a modder wants a new group of NPCs, say, on motorbikes, and finds a coder developing an AI for them. Then he needs a new index (n), of course, so as to not break already used indices. So now some NPCs have their ai_index set to n, and we add to the ini
AI_INDEX_n = MOTORBIKE_AI_1

As far as I can tell, we are set for all types of new stuff Smile

Having the militia change their behavior if the player shoots at them can be done in different ways. We could either change the Concrete Factory at the appropriate index to ReallyAngryMilitiaPlanFactory, or the "default" militia plan factory already takes the player's actions into accout (when we change the factory, it would detect at the next plan update call that the plans were made using a different factory, and generate completely new plans). Both is equally possible, and I personally would decide depending on the size of the DefaultMilitiaPlanFactory's size (i.e., don't make it too complex, but try not to have too many factories either). It isn't a decision that has to be made up-front.


Quote:
Why not reeavaluate plan execution as it is currently done?

Well, "plan re-evaluation" will be performed, as I said, but the current way of doing it is a mess, as best I can tell. But in any case, whenever somethin unexpected happens (with the meaning of 'unexpected' depending on the implementor of a Plan::execute() function in my current proposal, which is not very elegant, but by far the simplest way I can imagine), the plan is fead into the factory again and changed. Or not. The ChosenOne seems not to value his life or anything, we can emulate that... [for the non-AI-coders: the 'ChosenOne' is the soldier chosen to press the panic button. He even magically gets a key for all doors when he is chosen.]

Quote:
It can be reasonable to make hundreds of decisions in a single turn.

Can it ever be reasonable to make, in one turn, more decision changes than you have action points? But that's not the point, I think you misunderstand. I don't intend to cut single plan re-evaluation into slices. The Round Robin is meant to be performed if *nothing* unexpected happens. Imagine this: a squad of 12 soldiers on bigmaps patroling in a V-formation. The first one takes his turn, goes for all his APs along a path. Then the next, and so on. The last one has NV gear and detects, after one tile, the player. Now, the other 11 soldiers are far, far away and have no APs left. Instead, I suggest we let them move only for a part of their APs, even if they *don't* detect anything. Now, they have 90% of their APs left to attack the player when the last soldier in the squad detects him.

CapnJack, as said above, I'm currently not much concerned with concrete AI behavior (it is too far in the future from my point of view), but with a software platform allowing all sorts of fancy stuff (I also never played The Sims, I just read an article about it back then when the first game appeared - so I can't tell anything about the whiteboard AI architecture in practice, but I liked the idea back then from the theoretic standpoint; I'm not sure if I see it the same way now, though). But given enough time for the architecture to evolve, a scripting interface would be a rather trivial task. Writing good scripts, on the other hand...

Edit: Flugente, I totally forgot to thank you for you kind offer to support this. It really increases our chances of success tremendously. So, thanks :haloangel:

[Updated on: Thu, 11 April 2013 23:46] by Moderator

Re: Tactical AI: architectural redesign[message #317351] Thu, 11 April 2013 23:56 Go to previous messageGo to next message
DepressivesBrot

 
Messages:3801
Registered:July 2009
It was said in the past that a scripting language would be too slow to handle the AI, what's your take on this?

I'd also suggest using a new ini for your AI_Index_# stuff, depending on how many entries you end up with. Poor options.ini is such a big and convoluted file already that we shouldn't add specialty stuff few players would ever (dare) touch.


Re: Tactical AI: architectural redesign[message #317356] Fri, 12 April 2013 00:22 Go to previous messageGo to next message
Sam Hotte

 
Messages:2020
Registered:March 2009
Location: Middle of Germany
Though not being able to support this project with input to content, I support the idea and the concept of restructuring AI to enable easier coding and adding to AI. :super:

Also seconding Depri's proposal of not "exploding" options.ini with this ... Smile
Re: Tactical AI: architectural redesign[message #317357] Fri, 12 April 2013 00:47 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
Yeah, I also thoughth about splitting the options.ini (not only regarding AI stuff, but in general). There are some pros in having the things all in one place, but having unmaintainable monolithic god structures isn't so nice, on the other hand. Anyways, while I haven't yet looked at the place in the code where the options are processed, I'm sure it can be split/changed comparatively easily (perhaps, instead of an .ini file, an xml would be a more suitable choice? I'd have to thinks about that, but xml *would* allow more structure, inheritance in attributes, ...)

Anyways, scripting the *whole* AI doesn't seem feasible, but we could
(a) use scripts as a "special case", like for the Queen, limited to a few (5?) NPCs per sector without major performance hits. Well, depending on script complexity, that is.
(b) if they are really "that needed", we can always pre-compile them.

I'd say it boils down to script complexity. They can not be a substitute for a "real" AI; but then, they are few in numbers and could, if carefully crafted, utilize "speedy" ways to do things (If you have ever worked with Matlab or similar tools, you know that achievable speed depends solely on the question if you solve your problem in the way the developers intended it to be solved; multiply two matrices with built-in routines, you won't find any faster code [it uses blas and lapack, optimized over the last 35 years or so]. Do it home-brew style using script loops, and you wait forever)

The new architecture encourages scripts, actually. A ScriptFactory can produce a plan based on a script, and once constructed, the plan has no speed penalties. And a scripting language could develop natuarlly around defined Plan subclasses (which are needed anyways, scripts or no scripts). Any new Plan subclass could be made available in the scripting interface easily. Of course, the "update" method requires some thinking (but that is true for any scripted event; what *do* you do if things don't go as planned in the script?)

Hope that answers your question Wink
Re: Tactical AI: architectural redesign[message #317388] Sat, 13 April 2013 13:56 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
So, it's me once again. Building the code after the slightest change in any header (which happens in most svn updates) requires some 5h on my setup, making the development cycle somewhat tedious. Trying to understand the source of the problem, I looked at some compile-time dependencies. Here an example from Tactical/XML_Sounds.cpp

#include "sgp.h"
#include "Sound Control.h"
#include "overhead types.h"
#include "overhead.h"
#include "Event Pump.h"
#include "weapons.h"
#include "Animation Control.h"
#include "sys globals.h"
#include "Handle UI.h"
#include "Isometric Utils.h"
#include "worldman.h"
#include "math.h"
#include "points.h"
#include "ai.h"
#include "los.h"
#include "renderworld.h"
#include "opplist.h"
#include "interface.h"
#include "message.h"
#include "campaign.h"
#include "items.h"
#include "text.h" 
#include "Soldier Profile.h"
#include "tile animation.h"
#include "Dialogue Control.h"
#include "SkillCheck.h"
#include "explosion control.h"
#include "Quests.h"
#include "Physics.h"
#include "Random.h"
#include "Vehicles.h"
#include "bullets.h"
#include "morale.h"
#include "meanwhile.h"
#include "SkillCheck.h"
#include "gamesettings.h"
#include "SaveLoadMap.h"
#include "Debug Control.h"
#include "expat.h"
#include "XML.h"
#endif 


Toying around with it a little bit I found out that this is enough:
#include "sgp.h"
#include "Sound Control.h"
#include "expat.h"
#include "XML.h"


So how do you do it? Is there some secret header pre-compilation option (actually, there is PRECOMPILEDHEADERS, do you use that)? I realize that my build environment uses a virtual machine, which slows things down. But that's a factor of what, 5 perhaps? So you still would need about an hour to re-build the binary for every ever-so-tiny header change, which I find pretty unacceptable (sure, every project has *some* headers that require everything to be re-built when they are changed. But here, *every* header seems to have this not-so-nice property).

Anyways, in light of the lengthy build cycle on my setup, cleaning up these includes doesn't really seem to be the best thing for me to do (plus, I seem to be the only one who currently has any idea on how to tackle the AI re-design, so I should probably concentrate on that). There aren't any advanced coding skills required for the task either, so probably some of the nice folks wanting to help the AI development but "not having the proper skill set" could help me out? I'll even mention you in the contribs file for the AI code :bow:
Re: Tactical AI: architectural redesign[message #317398] Sat, 13 April 2013 20:34 Go to previous messageGo to next message
DepressivesBrot

 
Messages:3801
Registered:July 2009
So how would that hypothetical helper do that? Just delete includes and see if it still compiles?


Re: Tactical AI: architectural redesign[message #317399] Sat, 13 April 2013 21:05 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
Well, in case of the XML_Sounds.cpp I had a pretty good idea from the filenames what would be needed and what not. But indeed in the first try I removed two headers that were needed; the compiler complained about undefined types - so I looked where they were defined and had my two headers in the next run.

So, my strategy would be to remove rather a header too many, see what the compiler is missing, and then add what is needed (often, an include of the prviously included file will suffice). Also, "my" compiler (g++) can produce include dependency graphs, which can be quite helpful. Unfortunately, it doesn't work on the Windows-only code (the problems range from improper cases in the filenames to Windows-specific headers and non-ISO14882 compliant constructs like double underscores, which are reserved for compiler implementation). But probably a similar tool exists for Windows?
Re: Tactical AI: architectural redesign[message #317425] Sun, 14 April 2013 17:16 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
OK, I'm starting to remember now why I haven't used Windows for the lasst ten years or so. What the f*ck is wrong with these people? One day you write code, followed by two days to find the settings in Visual Studio... well, I got it to compile here, but somebody better double-check the settings. I'm rather sure that I messed up *something*. Furthermore, I added the new "Project", as VS calls it, only to the 2008 edition stuff (Solution or whatever it is called). If somebody could kindly add it to the other .vsproj files, that would be awesome.

That being said... I put the new AI "base" framework in place, so that everyone can get a better understanding of what this thing means for further AI development. I hereby invite anybody interesting in the latter to have a look at it and give feedback here; you might want to start from the source code repository's Build/ModularizedTacticalAI/readme file.

While I tried to confine my actions to said subdirectory, I had to integrate the system with some already existing code. Here is the ChangeLog:

- Added bAIIndex to SOLDIERTYPE in Tactical/Soldier Control.h and decreased the ubFiller accordingly.
- Adjusted SOLDIERTYPE::Load() in SaveLoadGame.cpp to read the bAIIndex or set it to 0
- Deleted assignment operator and copy constructor from SOLDIERTYPE; they were redundantly coding the default behavior
- In TacticalAI/AIMain.cpp, HandleSoldierAI(), the "main" entry point for the new AI system was added
- I moved (as in svn move) SCREENS.cpp to Screens.cpp, same for .H
- I removed an #include of a compilation unit (!!!) from Strategic/XML_CoolnessBySector.cpp (Facilities.cpp still includes .cpp files...)
- I removed "some" includes in Tactical/XML_Sounds.cpp (see some posts above)
Re: Tactical AI: architectural redesign[message #317428] Sun, 14 April 2013 19:09 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
OK, risking a soliloquy here, let me explain what the new system currently does, how it needs to be improved, and what the consequences might look like.

For the most part, the architecture is as described in my second post on this topic. For details that needed refinement during implementation, please have a look at the doxygen-documentation in Developer_Docs/ModularizetTacticalAI in the svn source code repository. On the "user" side of things, a new ini file (AI.ini) was created in the Data-... directories. The file maps indices (between 0 and 65535) to strings, the strings being names of "Plan Factories". Here is the default file:
[Modularized Tactical AI] 
; DO NOT, repeat NOT add 'comments', spaces, or other stuff after the factory
; names. The ini reader doesn't separate it from the data string.
; Factory_n is used for any npc with bAIIndex set to n. Currently, the index is
; copied from bTeam; I hope that somebody can integrate it into the map editor
; soon. Then you can add any number of indices (up to 65535, that is), but they
; must be consecutive.

; Currently implemented factories:
; NullPlanFactory - makes an NPC do absolutely nothing
; LegacyAIPlanFactory - makes an NPC behave "as before"

; Increase NumFactories accordingly
NumFactories = 11

; not used
Factory_0  = NullPlanFactory

; 'OUR_TEAM', so not really used either (?) 
Factory_1  = NullPlanFactory

; 'ENEMY_TEAM'
Factory_2  = LegacyAIPlanFactory

; CREATURE_TEAM
Factory_3  = LegacyAIPlanFactory

; MILITIA_TEAM
Factory_4  = LegacyAIPlanFactory

; CIV_TEAM
Factory_5  = LegacyAIPlanFactory

; PLAYER_PLAN (?) 
Factory_6  = LegacyAIPlanFactory

; LAN_TEAM_ONE
Factory_7  = LegacyAIPlanFactory

; LAN_TEAM_TWO
Factory_8  = LegacyAIPlanFactory

; LAN_TEAM_THREE
Factory_9  = LegacyAIPlanFactory

; LAN_TEAM_FOUR
Factory_10 = LegacyAIPlanFactory


As explained in above file, the indices for the AI factory to use are currently, lacking other data, copied from the team. It is a big fat TODO, for both coders and mappers, to change that. Someone - I'm hoping Flugente can help here - needs to add a possibility to editor to set this index to something different than bTeam.

Regarding the plan factories... there are currently two of them, both trivially creating corresponding plans (the NullPlan and LegacyAIPlan, respectively). The null plan simply calls EndAIGuysTurn() for the npc the plan is for. The legacy AI plan calls the functions formerly called to handle the AI, i.e., it is a simple wrapper. Changing "overall" behavior thus becomes trivial, to make all civilians always stand still and not do anything, you could change Factory_5 to NullPlanFactory. Of course, something that makes more sens, like a "cow AI" limiting cow movement to grass tiles or something, would require a new factory and appropriate plans to be implemented. But once done, and assuming someone changed the AI index of cows to a different value that that of other NPCs, it could be done via this file.


What now needs to be done is a division of the current AI code into "appropriate" parts. This part requires some thinking, because said division is not arbitrary (e.g. we cannot easily divide the color levels of the AI) and out aim is a maximum in flexibility - which translates to a maximal reusability of plans. My suggestion would be to split the AI in "civilian", "enemy" and "militia" parts. Then, different people can take these parts further apart, until a set of "elementary plans" (on a level of "go to place X", "attack Y", "seek cover" and so on) is available.
Re: Tactical AI: architectural redesign[message #317433] Sun, 14 April 2013 22:32 Go to previous messageGo to next message
RoWa21

 
Messages:2039
Registered:October 2005
Location: Austria
@feynman: I am currently modifying the VS 2005/2008 project files to get the new project included and to get it compiling without errors. Once it is done I will post again ...

[Updated on: Sun, 14 April 2013 22:49] by Moderator



Re: Tactical AI: architectural redesign[message #317435] Sun, 14 April 2013 23:01 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
Thanks RoWa21. After a rather messy 2008/2010 conversion I'm going to switch to the Visual Studio 2010 version (2013 didn't work, as posted above). Although I don't plan to add any other libraries in the near future, so this will hopefully the only time I mess up the repository for everyone... sorry about that btw :oops:
Re: Tactical AI: architectural redesign[message #317436] Sun, 14 April 2013 23:26 Go to previous messageGo to next message
Flugente

 
Messages:3387
Registered:April 2009
Location: Germany
I modified the VS2010 settings (thanks to our resident dutchman).

Savegames are broken, I'll check wether that can be fixed.


Re: Tactical AI: architectural redesign[message #317439] Mon, 15 April 2013 00:48 Go to previous messageGo to next message
RoWa21

 
Messages:2039
Registered:October 2005
Location: Austria
Project files are updated


Re: Tactical AI: architectural redesign[message #317452] Mon, 15 April 2013 19:44 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
Many thanks to everyone cleaning up my mess. Flugente, good call on the padding problem. I thought I had it working without breaking saves, but after so many trials I just didn't know which saves belonged to which version, I guess.

I'll continue with an AI system breakdown into pieces suitable for the new architecture; I think this will best be done on a multi-iteration, top-down approach (i.e., first split it in, say, enemy, militia, and civilian AI, then refine the parts into walk, attack, talk and so on), which fits the architecture (plans are supposed to be multi-level) and also allows a continuous integration "commit early, commit often" policy. While doing so, I am pretty sure that I also need to refine the interaction between the new ModularizedTacticalAI subsystem and "the rest of the code", which I'll do along the way, trying to break as little as possible (probably should change my nick to Maddog, though, who is, after all, Vice President of wrecking stuff). It'll also take time, the code is a real mess (but you already knew that...).
Re: Tactical AI: architectural redesign[message #317540] Thu, 18 April 2013 17:26 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
Greetings,

so, I've got good news and bad news. The good news is that I've managed to get two other hooks for the new AI in place, and I'm pretty sure that now the architecture is pretty much in place. The bad news is that the code base isn't making a clean transition very easy... I've tried, as a proof-of-concept experiment on the soundness of my architecture, to completely port the AI code of one NPC class, namely the crow, to the new system. Here are the results.


So, how are crows implemented? Crows have, like -- I think -- all NPCs, two "reasons" to do anything. One "initiative"-type action is performed by what is officially labeled as AI code. It is triggered from ExecuteOverhead() and quickly descends into CrowDecideAction[Color]() (with color being green, yellow, red or black, the well-known alert status). The other one is unfortunately not labeled so, and the unsuspecting programmer can easily overlook it. In fact, even if you know *what* you are looking for, it still is kind of hard to find. This is a "interrupt"-type *re*action, triggered from HearNoise(), which is not descending anywhere, but directly calls, in a very spaghetti-code-like manner, CrowsFlyAway().

Summary: currently, crows' DecideAction() is called "polling" style, allowing them to show initiative (which they use to find corpses, land there, and pick on them). And in a totally unrelated piece of code, the routine that informs NPCs about a noise, CrowsFlyAway is called, so that when they hear something, they fly away.

Now, suppose we wanted a new type of NPCs similar to crows, but behaving slightly differently. A parrot, who flies not towards corpses, but towards the player, and flies away not when he hears something, but when he sees a (blood-)cat. If this can't be done really easily, my design stinks and should not be used. So, let's try and find out!

Using the structural requirements for the architecture laid out in my second post, the semantics of crow actions, and above goal in mind, how is the crow AI best re-designed? We do recall that factories decide what is to be done - i.e., what plan to instantiate - while plans are to decide how it is done. I decided to give the crow three Plans, namely the CrowSeekCorpePlan, the CrowPickOnCorpsePlan and the CrowFlyAwayPlan. I've decided not to use an own PlanFactory, like CrowPlanFactory, the current implementation of the LegacyAIFactory is so simple that it can handle the extra case of generating and updating a crow plan. Besides, crows don't have their own AI index yet, making an own factory for them pointless.

So here is (part of) the code for the LegacyAIFactory, i.e. the code for deciding *what* to do:
Plan* LegacyAIPlanFactory::create_plan(SOLDIERTYPE* npc, const AIInputData& input)
  {
      ... 
      if(npc->ubBodyType == CROW)
      {   
          CrowSeekCorpsePlan* seek_corpse = new CrowSeekCorpsePlan(npc);
          CrowPeckPlan* peck = new CrowPeckPlan(npc, seek_corpse->get_corpse_grid());
          PlanList* find_supper = new PlanList(npc);
          find_supper->add_subplan(seek_corpse);
          find_supper->add_subplan(peck);
          return find_supper;
      }   
      ... 
  }

I intentionally didn't comment the above code. If you can't figure it out by the identifiers, I've failed my task and will leave here in shame.

As you can see, the factory decides upon plan creation that crows should find a corpse, and then peck. The old code had no way of remembering the body to peck on, btw, meaning (a) a high-cost operation for finding the next corpse was called multiple times and (b) there was no way of controlling that the crow really pecks on the body it did go to, if several corpses were close together. Now for crows, it doesn't matter, obviously. But for other plans, it will.

Now, you will have noticed that crows don't plan to fly. Well, they shouldn't, because they only do when disturbed by a noise, for which we obviously can't plan ahead. When a noise is heard by an NPC, it triggers the update_plan method of its associated factory:

Plan* LegacyAIPlanFactory::update_plan(SOLDIERTYPE* npc, const AIInputData& input)
  {
      ... 
      if(npc->ubBodyType == CROW && input.is_sound_event())
      {   
          if(!dynamic_cast(npc->ai_masterplan_)) // make sure this crow doesn't already plan to fly away
          {   
              if(npc->ai_masterplan_)
                  delete npc->ai_masterplan_;
              npc->ai_masterplan_ = new CrowFlyAwayPlan(npc);
          }   
          return;
      }   
  }

Now, if that'd work, all would be well. Unfortunately, it doesn't. I did manage to get a hook into the hearing- and sighting notifications, so the update is called as it should. However, the execute()-method of the CrowFlyAwayPlan instance is called some half a minute later, when the game decides it is time to update the crow AI again. Now, I do hope that this problem is limited to crows, because enemies' execute() *is* called *IF* they do get an interrupt; but deciding that we do get an interrupt is *not* an AI decision (whereas we may very well plan, or update a global plan structure, if we hear something, even if we do *not* get an interrupt. The player has the same chance, after all, and it might become relevant later in a turn, when we, or an ally, does get an interrupt, or in the next turn).

So, while I did implement the CrowFlyAwayPlan, it isn't used currently. But if you want to toy around with the new AI system, you could re-write the crow AI so that crows fly away even when undisturbed after, say, five minutes. To do this, you would have to write an WaitPlan (which *should* be trivial, set bAction = AI_ACTION_WAIT and usActionData to the amount time you want to wait), and add the wait- and fly away plans after the peck plans in the find_supper plan composition (first code listing).


So, any comments, thoughts, death threats?

Cheers,
feynman

PS
I really think someone should add a parrot. It would not only be totally awesome, but he could also tell the player about all the latest features when talked to.

PPS
Haven't pushed yet, but plan to do so later today.
Re: Tactical AI: architectural redesign[message #317541] Thu, 18 April 2013 18:44 Go to previous messageGo to next message
tais

 
Messages:807
Registered:February 2008
Location: NL
/me hands feynman a wooden leg to complement the parrot

for the rest it all sounds good to me Razz


Re: Tactical AI: architectural redesign[message #317542] Thu, 18 April 2013 18:47 Go to previous messageGo to next message
DepressivesBrot

 
Messages:3801
Registered:July 2009
[needs animation]


Re: Tactical AI: architectural redesign[message #317589] Sat, 20 April 2013 13:29 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
Small update on the coding front again.
I've started to disassemble the militia AI for green alert status, trying to identify Plans, writing them down as such, and removing them from the rest of the AI code. I began with the POINTPATROL, but soon noticed that a much more general version is possible: the "MoveAlongWayPointsPlan", moving an NPC along waypoints. I decided to use a generic approach regarding the policy what these way points should be; for simplicity, generality and compatibility with the current code I use what C++ calls a "Range".

This makes both the MoveAlongWayPointsPlan and the patrol plan implementations (POINTPATROL, FARPATROL, NEARPATROL, RANDPATROL) trivial - the MoveAlongWayPointsPlan is trivial because it is no longer concerned with where the next point should be; it simply increases the iterator in the range, makes sure that the point is valid and the end of the range is not yet reached, and sets the target for the NPC to the value of the iterator. And the fun part is: the ranges themselves are even more trivial! As you know, pointers are models for the Random Access Iterator concept, and thus also the Input Iterator concept. So, to make the MoveAlongWayPointsPlan behave like the old POINTPATROL plan, we merely need to plug in the first and last way point stored in the NPC! (OK, we also need to loop, but that is taken care of in the plan update function). So, what about a random patrol? It's so simple that I'm nearly ashamed to write it down, but for completeness' sake:
class RandomPointIter
{   
    private:
    public:
        RandomPointIter() {}; 
        INT32 operator*() {return rand() % MAX_MAP_POS;}
        RandomPointIter operator++() {return *this;}
        RandomPointIter operator++(int) {return *this;}
        bool operator==(const RandomPointIter& other) const {return false;}
        bool operator!=(const RandomPointIter& other) const {return true;}
};

That's it. Plug this thing into the MoveAlongWayPointsPlan, and whenever it decides that we have reached one way point and should move on to the next, it will dereference an object of above class, which returns a random point somewhere on the map (if it is "reachable", in the water or whatever is not checked, but as you can see the solution for that problem lies in a highly encapsulated dereference function call of the iterator object, which means: to fix it, you don't have to know *anything* about the AI).

Of course, another iterator could iterate over an external file containing an arbitrary number of way points, as was suggested here

That, too, would be trivial. Or we can write an adapter for the iterator (similar to the well known reverse iterator adapter in the STL), returning an offset from another iterator's value, thus leading to several AI guys moving in formation.

Edit
Damn, I'm a genius. You don't even *need* an own iterator for an external file. Just use istream_iterator(fstream_of_your_file), and you're done.

[Updated on: Sat, 20 April 2013 13:34] by Moderator

Re: Tactical AI: architectural redesign[message #317618] Sun, 21 April 2013 18:06 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
OK, regarding the FlankPlan... I've looked some more at the current code. What it does is it looks in a very limited range (4 tiles) around the current position for the best "spot" to go to next. If none exists in the "desired direction", it aborts. It is thus not surprising that the current AI is completely inept to deal with longer range engagements.

Analysing the situation geometrically, this is what I came up with:

- At the time we "initiate" flanking, we have just realized a threat. So this threat is at some point on an imaginary circle around us, the 'event horizon', maximum hearing range or whatever. If we assume a linear trajectory of whoever caused the disturbance (it may be far fetched, but I don't see how we can do better), we can foretell the target's trajectory within a pi/2 margin of error to both sides, the mean being a path leading from the disturbance directly towards us (obviously, the object cannot move 'away' from us, because if it did, then the object would have been within hearing range before, and at this point we would not initiate flanking but would have done so before, when we first noticed the disturbance).
- Depending on the sort of noise we heard, we can project the target's speed, and thus the distance travelled in the last turn/second. This means that we know a half-circle the target is in for the next turn/second (don't take second literally, make it a 'time slice'). E.g., if it was a shot, the target is likely not to move, it it was a movement sound, it did and likely will move.
- If we want to get behind the target unseen on a shortest route, we'd have to go in what we can approximate as an elliptic curve. Given that we can only move along tiles, someone would have to implement something Bresenham-like to make a tile-list out of that...
- ...which we most likely could not follow anyways due to obstacles. I'm a bit lost here. There are beautiful path planning algorithms using the potential field method, which I'm pretty sure would yield excellent results in this case, but given that nobody has managed to get a decent A* path search in the game makes me wonder if that is probably not a bit too high a goal.

- Anyways, as an "intermediate" solution (yeah, right...), I propose as input to the FlankPlan a threat position, a target position (where we want to be without being seen from the threat position) and a radius, which is the guessed 'event horizon' of the target - i.e., it depends on the guessed sight and hearing range of the target. Then we perform a straight-forward sampling of the resulting "optimal" trajectory (i.e., without taking any obstacles into account) and try to connect them using the legacy path search. We do this for both left and right flanks and take the path that is cheaper/possible, if any is. Otherwise, we abort right *before we start*, contrary to the current implementation...

Any thoughts and suggestions on that would be much appreciated, as always.
Re: Tactical AI: architectural redesign[message #317623] Sun, 21 April 2013 18:28 Go to previous messageGo to next message
Sam Hotte

 
Messages:2020
Registered:March 2009
Location: Middle of Germany
feynman
- At the time we "initiate" flanking, we have just realized a threat. So this threat is at some point on an imaginary circle around us, the 'event horizon', maximum hearing range or whatever. If we assume a linear trajectory of whoever caused the disturbance (it may be far fetched, but I don't see how we can do better), we can foretell the target's trajectory within a pi/2 margin of error to both sides, the mean being a path leading from the disturbance directly towards us (obviously, the object cannot move 'away' from us, because if it did, then the object would have been within hearing range before, and at this point we would not initiate flanking but would have done so before, when we first noticed the disturbance).

That's not as obvious to me since the opponent causing the threat noticed could have sneaked to his current position unnoticed, causes the current threat (took a shot, throw grenade, is heard moving now) and retreats (to some cover or so).
So I'd say the threat I want to try to flank now can very well move away from me in the imminent future. However threats coming closer have higher priority to counter, so, yes, the half circle towards me has higher priority to be considered IMHO.

I don't know what has already been tried to improve path finding and the like, so I'd take the very uneducated guess that the fact nobody has ever managed to get a decent path search implemented is no valid indication on how difficult this might be ...
Re: Tactical AI: architectural redesign[message #317625] Sun, 21 April 2013 20:08 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
As I said, I'm assuming a linar trajectory - a merc in motion remains in that motion (unless stopped by a bullet). At the point that someone has taken a shot at us, we are no longer in the position to flank them. So yes, I think at time point we initiate flanking, the threat must be far enough away that my presumption should hold. If not, we have made an error in judgement. Well, shit happens. (It's not like we are going to tell everyone what we tried to do; to the player it will just look like a redshirt walking in a what turned out to be not-so-optimal direction, which is still far better than the current osciallation and whatnot. Plus, for insane, we could use a cheating AI that knows the current position and looking direction of the player, making the "right" choice more often).
Re: Tactical AI: architectural redesign[message #317649] Mon, 22 April 2013 17:21 Go to previous messageGo to next message
Sam Hotte

 
Messages:2020
Registered:March 2009
Location: Middle of Germany
Ok, wasn't Aware that 'flanking' would just apply to "i heard something but have not been shot at (nearby) myself).
So, yes, assuming the half circle towards me seems most important to be considered. Smile

BTW: I'd accept some minor cheats of AI on higher difficulties (like: if they hear something, the ones actually hearing the sound do always know the exact spot the noise emanated from) to keep up the challenge ...
Re: Tactical AI: architectural redesign[message #317863] Thu, 25 April 2013 16:47 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
Having worked my way through quite a bit of the code both in breadth and in depth, my opinion is this: cleaning the code up without breaking it can't be done, classical refactoring is out of the question.

As I see it, we have three options. Number one is to stop right now. A new Jagged Alliance was announced by Full Control, so why bother improving the old one anyways?

Number two is resorting to copy-and-paste programming, the cardinal sin in writing maintainable code and one of the reasons the code is such a mess as it is. The option sounds good enough from a functional point of view - keep the old AI and add a shiny modularized new version, usable in parallel - but beneath the surface, it still is a total mess with twice the maintenance requirements, making it much harder to add stuff (like better NCTH support), as it has now to be added to both subsystems.

And finally, number three... screw the legacy functionality, let it break, we don't care. While the new AI is being developed, the old functions would remain as a copy (just like option 2), but as soon as the migration (and testing) of a certain part of the AI is done, it goes away.
As Flugente suggested, for this option a large part of development will take place in a branch (actually, another repository, as I am currently the only one working on that thing I'm using my own local one), however, it would be foolish to think that one can develop a new AI, substitute it for the current one, and all is well. Integration would have to take place feature-wise so as to allow testing (e.g., I substitute the 'green militia behavior' by the new system, commit, the community tests, once done, the legacy code for this specific behavior goes). Of course, this has to be done in a way that does not break the overall AI, but would inevitably change some of the behavior that IMHO simply isn't worth the hassle of keeping.
A large part of these changes would be subtle, and I doubt anyone would notice (like, currently we'd stop flanking if the energy goes below 75%; I'd change that to "don't start a new flanking plan if the energy is below 75%, but once started, do it, and rest only when at a 'way point' [which could be some tiles away from where we would have rested otherwise, but not so far that we are completely out of breath]". There are some "early exit" conditions for the AI code that would require considerable effort to implement in each plan, but have no substantial benefit). Of course, changing but the tiniest thing can have unforeseen side effects, which is why early integration and regression testing by a large number of players is essential in this case.

So, what would *you* prefer?

Edit... as suggested by DBrot, I inserted some line breaks Razz

[Updated on: Thu, 25 April 2013 17:46] by Moderator

Re: Tactical AI: architectural redesign[message #317864] Thu, 25 April 2013 17:03 Go to previous messageGo to next message
DepressivesBrot

 
Messages:3801
Registered:July 2009
I prefer line breaks, but that's just a sidenote.
Number one isn't really pertinent. For one, FC themselves are aiming at end of '14 or later if they get the funds to do more stuff. They are acknowledging 1.13 as an unreachable standard which means we probably keep tinkering with it until the more ambitious coders get their hands on the JA:F code.
Option two would be the classic JA2 approach ... check the CTH function if you haven't already Evil or Very Mad
So I guess that leaves number three as the most attractive, seeing that nobody will really shed a tear after the old AI. However, don't you dare hiding your stuff somewhere on your drive just to disappear in a month or two.


Re: Tactical AI: architectural redesign[message #317867] Thu, 25 April 2013 17:27 Go to previous messageGo to next message
Sam Hotte

 
Messages:2020
Registered:March 2009
Location: Middle of Germany
2nding Depri once again here; I'd also vote for #3.
Re: Tactical AI: architectural redesign[message #317884] Thu, 25 April 2013 18:29 Go to previous messageGo to next message
Gambigobilla

 
Messages:717
Registered:July 2008
The problem is JA doesn't have an artificial intelligence, it has artifical stupidity. I wouldn't mind if someone made it vanish.
Re: Tactical AI: architectural redesign[message #317921] Thu, 25 April 2013 23:36 Go to previous messageGo to next message
The_Bob

 
Messages:400
Registered:May 2009
Location: Behind you.
Is there any legacy functionality that is actually worth saving?
Stuff that is "scripted" or the game depends on it for things to play out as intended?
If you identify any such instances, can they be preserved while you gut the actual combat AI code?

Re: Tactical AI: architectural redesign[message #317960] Fri, 26 April 2013 09:26 Go to previous messageGo to next message
pheloncab

 
Messages:278
Registered:August 2004
Location: So. Cal. or texas
I vote on option 3 with its own trunk on the SVN so others can help if they want, especially once it gets towards the bug squashing phases or integrating it with new features.
Re: Tactical AI: architectural redesign[message #318014] Fri, 26 April 2013 22:20 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
What a week... if someone finds the guy that invented meetings, please shoot him for me, then replace Deidranna with a model of that bastard.

But more to the point at hand - thanks for the input. It's settled, then, we accept that some of the changes to the AI are not optional.

Regarding a more public development: for the time being, I'd suggest that anyone who wants to get involved just says so (I'd be glad to have some help and discuss code changes), because in this early phase I'm adding some new files, and updating the three MS projects is error-prone, especially since I can only test one of the setups. So while I do commit early and often to my local repository, I want to limit the number of times I break the project files for everyone else Wink (plus, it's not like I'd have to fear an overly complex merge after changes to the AI). So I'd only do it if it is actually needed.

A first test will "soon" be committed to the public svn, but I will only change green militia AI in this one. The nice thing about it is that it has minimal impact on combat (except the starting positions of the militia), but we can test the overall setup, detect possible speed issues etc., and have the perfect platform to experiment with patrolling/movement patterns (it is kind of hard to observe real-time enemy movement in green mode...). Plus, the current green militia AI does pretty much nothing, so a "legacy" version can be provided easily. Those willing to test the new version and comment on the movement patterns, which I'd later also use for enemies, can simply change the AI.ini

Edit @The_Bob: There are some "obvious" things like the Queen going to the staircase, which I will obviously try not to break. But this is indeed something that will require extensive testing, because decision making and actions are so mixed that it is completely impossible to tell all the implications of a code change (e.g., I wanted the movement plan to accept, as parameter, if we want to walk, run or crawl; the SOLDIERTYPE has a fitting parameter. But if you set it, you find out that it gets reset in a function named NewDest() - a function doing nothing more actually - and it chooses based on the question how cunning we are [which, in turn, makes a not too small portion of the legacy "decision making"-labelled code do absolutely nothing], but *not* based on the value of this parameter. And the function gets called - surprise - ExecuteAction())

[Updated on: Fri, 26 April 2013 22:26] by Moderator

Re: Tactical AI: architectural redesign[message #318022] Fri, 26 April 2013 23:29 Go to previous messageGo to next message
Flugente

 
Messages:3387
Registered:April 2009
Location: Germany
feynman
(it is kind of hard to observe real-time enemy movement in green mode...)
On the contrary. Use a covert ops expert, you'll have all the time in the world Smile

(Though be careful with walking, making too much sound can push the AI into yellow state).


Re: Tactical AI: architectural redesign[message #318085] Sat, 27 April 2013 17:50 Go to previous messageGo to next message
lockie

 
Messages:3928
Registered:February 2006
Location: Scotland
Ok , maybe a day late , problems with web connections (using a tablet just now , it's slow going) 3 looks best bet and might score you a job on a shiny new game .... :naughty:


Re: Tactical AI: architectural redesign[message #318130] Sun, 28 April 2013 15:49 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
OK, some good news again. I have extended the design by "plan groups". These enable coordinated update- and execution operations of plans owned by different NPCs, like patrols in formation. While implemented
rather straight-forward and not-so-optimal complexity-wise, but for the handful of NPCs the game has to control at any time, this shouldn't matter.

To call actions "simultaneously" within a group, the 'execute' and 'update'-functions of plans and factories, respectively, would have to call each other (the execution of a plan detects that it is finished, leading to a group update; the update requires new 'what-to-do-next' kind of planning, being done in the factories update routine), leading to the circular calling problem described in my second post (if the update function decides to delete the plan which called the update in the first place, the result is undefined behavior). I've circumvented that by setting the AI refresh time to 0 for the following call, misusing it as a function calling queue. Implementors of subsequent factories using group actions will have to be careful in this respect.

Anyways, although the current implementation is not very exciting, it shows the feasibility of group behavior, be it coordinated flanking, a 'buddy system', sniper/spotter teams or whatever. The game was however not built for a precise (movement) coordination, one example of this is the slightly different movement speed of NPCs with different agility. My implementation does not consider that, or the grid, or obstacles. It computes the positions in the euclidean plane. So one soldier in the patrol might move into a building etc. Improving this will be a lengthy process, but it would be conceivable to
- assign each NPC in a group the average agility of the group; the movement speed should then be equal and the impact should be minimal
- hand-place the patrol points to avoid obstacles or compute the random patrol points so that each NPC in the group can reach the target with its own offset. This would be computationally intensive, so it sho
uld probably be done in a pre-processing step. But hand-placing patrol points so that they have enough space around them and don't lead through buildings shouldn't be too hard.
- write a coordinated path search, that detects when one NPC in a group has to go around an obstacle and lets the rest of the group wait until the detour is finished. Good luck with that.

...however, this is something I won't do (...anytime soon) as this isn't part of the refactoring.

The next problem I'm facing is (re-)initialization. NPC's plans need to be stored to and loaded from save games, which will be tricky (well, they *needn't* be stored, but then a coordinated attack would likely lead to pretty stupid behavior if interrupted by saving/loading).

@lockie: Don't kid yourself, game development is a hard and underpaid occupation. As a programmer, you can easily get a job with three times the payment and half the amount of work if you can do a half-decent job as game developer. Well, OK, probably not half the amount of work...
Re: Tactical AI: architectural redesign[message #318206] Mon, 29 April 2013 20:12 Go to previous messageGo to next message
feynman

 
Messages:38
Registered:October 2010
I've got the ClimbPlan working now. The code was partly broken in the legacy implementation - in green mode, militia would never climb, although the intention was clearly there (it would probably have worked with the A* shortest path algorithm, but that wasn't used, and the other one doesn't set MAPELEMENT_EXT_CLIMBPOINT). And not only does my implementation fix it, but it also should give a speedup in finding the climb spots - the old code looked at each and every tile grid in a certain area (20x20=400 tiles), whereas I only look at the climb spots defined by the buildings, and there aren't soooo many in each map. Yay.
Re: Tactical AI: architectural redesign[message #318210] Mon, 29 April 2013 20:41 Go to previous messageGo to previous message
Durak

 
Messages:57
Registered:April 2010
Your other thread may be more appropriate for my small question, but it's not in line with your latest post here, so:

Will jumping through windows be possible for the AI ?


cheers
Previous Topic: (More) questions regarding coding style and cosmetic changes
Next Topic: I'm putting an end to save-file compatibility breaks, if noone minds...
Goto Forum:
  


Current Time: Fri Aug 17 06:28:23 EEST 2018

Total time taken to generate the page: 0.01396 seconds