Bot Library
Blitz3D Forums/Blitz3D Programming/Bot Library
| ||
 Whos interested in AI Bot System suitable for first person and 3rd person games. A Bot System that can handle Finite State Machine Logic, 3D Navigation: Waypoints, Pathfinding & Collision Avoidance over Terrain and inside Interiors, & Model Animation Control. If such a Blitz3D library exists, can some please point me in the right direction. Thanks:) |
| ||
| I would mainly like fast 3D Navigation |
| ||
| I had some really good 3D Navigation A* PathFinding code I was working on for Project PLASMA. A Multi-tiered A* system suitable for both terrains and indoor levels with the assistance of waypoints. PathFinding is only one aspect of AI I Bot Library that I propose here. The Library would be completely independent and portable into any game. Other aspects are Event Detection and Locomotion/Animation. |
| ||
| Anyone who's not sure of the significance of what Frank appears to be offering, I wrote my own AI code which animated up to 12 characters, had waypoints, pause points etc. It only took about 3 months to write and finally debug, and needless to say, it is no way portable for someone else's code to use. Now I've found the need to completely rewrite my engine (for other reasons) from the ground up, and I'm dreading adding in my old AI code. Frank, I would gladly junk my code if you create a general purpose library that's dedicated to the job. |
| ||
| Sounds good frank, definately interested if the lib is portable into any game etc, would save me a lot of work on a Blitz3D project i'm currently working on. Blitz-Backdrop IndeED |
| ||
| Perhaps we can merge our current AI code/designs into the Bot Library? We can start with a description of the thinking characters in our games, in certain genres, etc. Then identify common requirements to develop a Library suitable for many types of games. For example, I desire FPS enemies to exhibit different attack and defense strategies: Sniper, Berserker, Chicken, Kamikaze. I desire Boss enemies to use patterned attack manuevers. This includes both acrobatic movements, weapons, and obstacles in the environment. Dynamic Paths created by a PathFinding algo are used to create a route of Waypoints that steer the bot from point A to Point B avoiding obstacles. These can be long or short paths depending on the need. Static Paths are manually built route of Waypoints that create special movement patterns (zig-zags, sqare-waves, etc) for bots to follow. The FMS Rules selects the reaction which control motor: movement speed, path, animation, based on sensors: collision detection, event detection, bot state change, self state change. Many other genres, besides FPS games could use a BOT set up like this. RPG games may probably have the BOT AI effect a DiaglogQA selection and display. |
| ||
| Difficult to know if I could contribute. As I said my code was so embedded as to be useless to anyone else. Also my characters were non-combatants. They talked to you if you clicked on them (preset speech different for each one), or said hello to each other if they collided. It would be interesting if you could also build those capabilities into your code. |
| ||
| Difficult to know if I could contribute. Ideas are good at this point. John, your characters sound like RPG type characters. I suspect that they will need navigation of some sort. Also, it may be desired to use various animated gestures to convey emotion or mood. This RPG AI could use the same FMS as Combatant AI with the addition of sensor for MouseClick events and Dialog selection. Behavioral Rules Artificial Intelligence Nodes System |
| ||
| I think one of the key elements that I would like if/when I rewrite my AI code will be to initialise a character which (using Star Trek Elite Force as a perfect example) can be combatants, or RPG characters with quite a lot of depth. As you say, my characters were RPG-like. They followed a 'script'. When clicked on, the app was aware at what point in the script the action had got to, and so the appropriate movement/dialog was triggered. A simple ini-file > array of char ids/wav file names/ action numbers sufficed. I'm actaully more interested in that than I am in combatants (but who knows, possibly my engine might be used for a game at some point). How does that approach sound to you? |
| ||
| John, I hadn't even considered Audio control. Thats why these discussions are so needed. I've also been researching various AI Middleware packages:1,2,3,4 that commercial developers use to help formulate a white paper for B.R.A.I.N.S (working title). I'll set up worklog to maintain news, updates, etc. We can use this thread for continued discussion. Although I have ideas for implementing Sensors, Motor, and Reaction sub-systems I would welcome input from others. With the most recent discussion I've given considerations for Audio, Networking, and Physics, features I previously overlooked. Another key feature of the system should be an AI Editor. It should support all Blitz3D animation formats. User-friendliness is always a priority, along side with features that do the job. A developer should be able to load the level map/terrain, drop bot models in, and start work. Editing of Animation data, sensor properties, static waypoint routes, reaction logic scripts should be key features. |
| ||
| I like the B.R.A.I.N.S. name and I *really* like the sound of a solid AI library. I'd love to contribute myself but anything beyond "goto wapoint/find next waypoint/goto waypoint/repeat" is beyond my skill set. But count me as very interested in the results. |
| ||
| Well, if I understand you correctly Frank, it's time to start a 'to do' or even better a 'should do' list. Where do you want to continue with this? |
| ||
| Dustin: "goto wapoint/find next waypoint/goto waypoint/repeat" Is exactly what we are doing. Even when using Pathfinding Algos to generate paths, the 'paths' will essentially be routes of waypoints.John, We can continue in this thread and list tasks as we go. I'll put the task we agree upon in the TODO list in the worklog - see Blitz3D Open Dev Projects Link Below. I would vote for basic 3D pathfinding to be a priority. Many of motor reactions for bots will rely on it. My first 3D A* was based on the typical 2D version. The only difference is find the path on X/Z planes, applying gravity to Y. This is good for Bots on land, but Aerial/Space Bots that can travel X/Y/Z need a different strategy. Waypoints are fairly simple. Add cost properties for distance and you can A* to find paths based on manually placed waypoints too. Add additional properties and they can be used to trigger actions/events. My first A* was really fast and versatile, but I ran into a collision bug that halted development. I will most likely revamp the code to get a foot ahead on pathfinding. The are other pathfinding algorithms out there perhaps we should discuss them as well. |
| ||
| As an advice, I would say, no matter what you code, do NOT use linepicks. I remember some time ago I started coding a simple pathfinding code and I used a simplified version of my a level to do it, then when I run the system in a 'complete' level the linepicks were killing the fps all the time. I changed the picks for 'shooting pivots to a certain distance' to check if they collide or not, this seems to work pretty much faster. By the way, what you are describing above is a d*** big amount of work, whish you luck :) |
| ||
| Sounds very interesting... |
| ||
| Eurythmia, i can recall doing some speed test with linepicks and the results were not satisfactory. You simply cannot use many of them. I plan to use a variety of collision detection methods to trigger bot reactions to include 3D geometric shapes and simple collision detection algos to simulate 'scanninig' zones. I will cannibalizing some old code for working out pathfinding. I do anticipate the Editor to be some major work. A good 3D GUI Lib and Editor System will make life much easier which what I'm shooting for with MAUI. |
| ||
| Can I just put the brakes on for a moment? I think there is a real need to go right back to the start and say 'what is the basic file format for character information?' My own method was to have an INI file with a list of characters by 'scene'. <Chars.ini> [IntroScene] 1 = Man1 2 = Man2 3 = Woman1 Then each char would have their own INI file: <Man1.INI> [Frames] 1 = IDLE,1,32 2 = WALK,33,50 etc [Sound] Collison = HelloHowAreYou.wav Click = DoYouWantToKnowTheWay.wav etc [Path] 1 = 100,0,100 2 = 200,0,200 etc [SpecialPath] - triggered by point in the plot 1 = 100,0,50,Plot1.wav (go here, say this, looking at cam) I think the decision about the file structure of the information is pretty crucial, even before you start listing actual attributes and behaviours. I found this worked well for me - it could have been gui-driven (most INI file structures lend themselves to that) but it wasn't necessary. |
| ||
| John, We could create a Level Profile, Group Profile, and Character Profile. The Level Profile will provide a list of Bot Groups in a level. The Group Profile will provide a template of properties and default values for characters. Characters Profiles define a Bot's property values independently. There are several formats we could use to export and import the data: xml, csv, ascii, binary. Selecting the format is the only difficulty I can see with data, not coding or organizing it. I believe there is an xml parser, csv reader, in the code archives. Its very easy to write a basic ascii and binary writer/reader module. We should also consider the roles of the Editor and Scripting. The Editor will facilitate the editing of Profiles, Bot Placement/Spawning, Animation and Audio Control, Waypoint Route Creation, Logic Script Building. All Logic should be scripted to meet the Sensor-Reaction-Motor AI Model. The Editor will provide point n' click for objects and controls which should ease Scripting Building. The scripting language will be very robust. Scripts will be stored plain ascii data files. We should also include a Q&ADialog Editing module. I expect coding the Editor and Sensor-Reaction-Motor AI Model will drive 'what and how' we save character information. Whatever preliminary format we come up with for now, is sure to change. I would be in favor of a format that is easy to export, import and expand. |
| ||
| "the Editor and Sensor-Reaction-Motor AI Model will drive 'what and how' we save character information" Ultimately, yes. But otherwise I disagree on this point. I think it's important to decide a style/format for information even before the start. I've always be in favour of the INI format, because it's so easy to track through and edit if necessary. When I've done this before I've started with a model INI file and flowchart/specification plan, then worked between them. Does that make sense? |
| ||
| When I've done this before I've started with a model INI file and flowchart/specification plan, then worked between them.Does that make sense? John, I would like to see the flowchart/specification plan. This would improve my visualization of your concept. I'm only guessing as to what type of data would be stored. The first difficulty I can see with data is selecting the format to read/write data in, not coding or organizing it. I would be in favor of a format that is easy to export, import and expand. I would prefer a commonly used format that folks can throw into a text editor if need be. It seems that a lot of folks are using XML and CSV (Comma Separated Values) formats to store data in an easy to read and edit in a text editor or spreadsheet/DB program. The INI files or Profiles could be in one of these formats. The second difficulty, is for us to agree as to what has to be stored. I would guess that a set of definable properties that represents the bots properties: {health, power, inventory, etc}, animation data, and logic script. The properties should be definable and configurable by the user, as bots will have different purposes. Some bots will have no animation and limited decision making (ie: Heat-Seeking Missiles). Some bots will function as a group (ie: a pattern of birds). So what ever format we agree upon has to be very expandable without having to modifying the hardcode. Your format will do if it can meet this need. Blitz XML parsers:1,2. |
| ||
| "Your format will do if it can meet this need." Hah-hah. Nice challenge, Frank. Point taken. |
| ||
| Hah-hah. Nice challenge, Frank. Point taken. No challenge. Seriously. I have to assume you have a parser/reader already available. It should not be too tough to produce a writer.What are your thoughts on XML? It could be used for INI Files. |
| ||
| John, I hope I did not offend you. I've aquired a XML Parser from the archives. I'm not all that familar with XML to be honest. However, I'm only considering future use of the Bot System and desire to design it around the most commonly used tools, etc. I cannot see any reason why we cannot use your format as our default. We can expand it as we go. Additionally we can include the export/import writer/reader modules for XML, CSV, Ascii formats. Whats your take on this issue. |
| ||
| Frank, not at all. I sent an email to your registered address and was waiting for a reply. ... Otherwise the way this is going, we'd need our own forum for all the communicatios. ;) |
| ||
| John, Got your email! I've replied. |
| ||
| Frank, Never got your email. Don't want you to think I've ignored you. Please send to john@... |
| ||
| John, I've resent the email. Please advise if you receive it. |
| ||
| Got it. Hope you got my reply. (Waving not drowning.) |
| ||
| John, I'm devising a plan by taking a hard look at many different 3D game genres, identifying the common AI applications, and creating a feature set based on those applications. Both Library and Editor is devised around the feature set. The current feature set: Scriptable Finite State Machine Logic 3D Path Finding Waypoint Editing Animation Control Diaglog System Editor The Finite State Machine is based on what I call a Sensor - Reaction - Motor 'Model'. A Sensor is a event check, collision check, and conditional check of object/bot/self properties. The Reaction is the action executed when a Sensor condition is met. The Motor is Dynamic/Static Routes and Animation control. The BRAIN is essentially a priortized queue of IF {sensor} THEN {reaction} checks. From this Model, I've been able to formulate some kind of stategy. First, each bot will need a dynamic set of properties that can be evaluated. The properties should be generic and store values like HEALTH, POWER, and INVENTORY. These properties collectively define the bots' state. The default values can be derived from a Group Profile/ini file. Sensors can also be defined as special collision objects attached or not attached to the model of the Bot. The objects can be virtual or geometric. These collision objects can be used for line of sight detection, or triggers. Second, each bot must have a Priority Queue to list Sensor checks. Sensor checks can be inserted and removed randomly from the list. more to come... |
| ||
| Damn, but you seem to have it well worked out! I can't disagree with any of your preliminary description. As you said my own needs were for non-conbatant RPG-type characters, so off the top of my head the sort of logic I would need is initially something like:- AGRESSIVE: yes/no (no) SHOOTABLE: yes/no (no) CLICKABLE: yes/no (yes) CLICKFUNCTION: (list) - probably an id, 0 to maxfunctions, where the id could be sent perhaps to a central message queue (like Windows SendMessage) then picked up and acted on by the coder's own code. In my case the bot speaks to the camera. Probably all functions like these can easily be agreed upon, I think we all know what we need, even if we haven't actually sat down before and made a list. But the one are that I have never seen (except in my own code, and in games like Morrowind) is the concept of a 'plot'. Again, off the top of my head this would be something like:- PLOT: yes/no PLOTSTEPS: 12 (or whatever), default is zero. PLOTACTION: 0 = (Walked over a square) > Do action x and increment plot count 1 = (Clicked on a door) > Do action x and increment plot count. The important thing about this logic is that all the bots 'know' what stage of the plot the game is currently at, and so if clicked on they will say the 'correct' thing, or react in the correct way, Or do both of those, and then increment the plot counter. As you've correctly guessed I've had all of the above in my own code, but hardly useable by anybody else - very enmeshed inside the main body of code. |
| ||
| John, I'm preparing myself to start some coding. I use lots of types to package objects neatly. How do you feel about types? From our previous discussions, I've identified some objects and sub objects that we could start coding: PROFILE BRAIN (Queue) BOT SENSOR WAYPOINT PATH DIALOG I have some code that can be used, but, more tweaking is necessary to figure out the exact properties that will go into the objects. I've been reading up on how AI middleware is implemented. http://www.gamasutra.com/features/20030721/dybsand_01.shtml. http://www.biographictech.com/pdf/AI.implant_Games_White_Paper.pdf http://www.renderware.com/ai.asp We are headed in the correct direction. |
| ||
| Frank, Yes types are ideal for this sort of work. I see a lot of code which uses FOR - EACH as the basic methodology, though to my shame I never got my head around that method. I always used counters, such as: Bot(cnt)\aggresive = 1 which I know is probably not the best way, as FOR NEXT etc allows you to create NEW types, but I could never understand how you indexed to a particulat individual one in order to delete it. What always puzzled me was that you could do a type = NEW Type method a few times, but then Blitz would not let you access the info as 'val = type(cnt)\value' - it didn't like indexing being applied to the structure, unless I'm missing something. Are you experienced in NEW, FOR, EACH? Which method will you be using? Not quite sure what you mean by PROFILE, but I can see that a PATH can be considered to be a separate entity which the bot merely accesses info from. Are waypoints separate from the path? Ah, yes, I think I just answereed my own question - a Path is a set of waypoints - a waypoint is a separate structure again, with many fields/conditions. And BRAIN (Queue) as a type - yes, I can see that you're thinking well ahead to the logic/structure required by all of this. Which I did NOT when I wrote mine. I just added to it as I went along. Big mistake. This needs planning (as much as possible beforehand). |
| ||
| John, I use a Array of Types with a custom 'ID' assignment method to provide fast random access and complete control. Its exactly like to your counter method with the additional field to store the ID. Type bot Field id% Field property$ End Type Dim botID.bot(100) ;array of types Global bots ;id counter Function botNew.bot() this.bot = New bot ;id assignment method bots=bots+1 this\id%=bots botID(this\id%)=this ;set default properties this\property="cogito, ergo sum" Return this End Function ;create an bot me.bot = botNew() myself%=me\id% i.bot = botID(myself%)I also use ID to reference other objects as an alternative to types within types. The idea of a PROFILE is based on your earlier concept of INI files with a template of default properties for a Bot Group. |
| ||
| Sorry, I still don't get it. I use: Dim Model.Jmodel(nNumModelsMax) For cnt = 0 To nNumModelsMax Model(cnt) = New JModel Next Then I access params as e.g. posx = Model(num)\x# etc, always using a specific index(in this case 'num'). You can see the difference between my code and your line: me.bot = botNew() I don't understand what 'me' is, or what 'i' is. Are these temporary values to acces the info in botID.bot(something). Sorry, this is getting embarrasingly close to asking for a Blitz tutorial. |
| ||
| John 'me' and 'i' are just temp variables. I attempted to demonstrate the various ways you could access and assign object properties. You can also do botID(1)\property$. We are doing exactly the same thing, cnt=ID. The only differences: 1. I add an additional field to the type to store the cnt value 2. I use a custom methods to produce the cnt value. The FOR...EACH just loops through all the objects in the collection. I use it to update all objects per update frame sync. |
| ||
| Ok. Is this the style you are going to use? For example, a collision usually returns a handle, so would you iterate completely through all the elements of the array until you find the handle, then pass back the id? Come to think of it, that's what I have to do anyway! I guess overall the logic is: a) Collision (or something) supplies handle b) Use handle to get id. c) Use id to e.g. make bot(id) speak or act. |
| ||
| John, Do you have a Instant Messenger? I have a yahoo and msn perhaps we can discuss realtime. The trick to performance is to minmize iterations and calculations. My goal is to iterate / update the bots, waypoints, paths, etc n/ frames. Since we will need to update the Bots at least once per frame. I'll call this the main update loop. We should attempt to process all the sensors - reactions for each bot the 'main' update loop. Instead of passing a handle and using it to get id, we could just pass the id. The method of collision determines how we acquire the handle or id. Collisions checks against the terrain and environment will have to rely on Blitz Collision, while checks against other bots, waypoints, etc will use maths collisions. Speaking of sensors, I'm learning that middleware AI Systems use Binary Decision Trees 'BDT' to manage Sensor/Reactions. I'm starting to see a coorelation between my 'queue' and BDTs. I can see BDT's being applicable to Dialog Management as well. I'm researching this. Related Articles on BDTs: http://www.generation5.org/content/2004/bdt-implementation.asp http://www.csc.liv.ac.uk/~frans/COMP101/AdditionalStuff/javaDecTree.html |
| ||
| Frank, "Since we will need to update the Bots at least once per frame. I'll call this the main update loop" - Agreed, and the implied logic. "Collisions checks against the terrain and environment will have to rely on Blitz Collision" - Fine by me, it's not let me down so far. "checks against other bots, waypoints, etc will use maths collisions" - Waypoints I can understand (that's how I do it). Other bots - ??? "BDT's" - I'll take your word for that. "Do you have a Instant Messenger? I have a yahoo and msn perhaps we can discuss realtime." - I've never used these. Let me investigate and get back to you. |
| ||
| Ran MSN, "You must download the latest version". Ok-download. Install. Reboot. Ran MSN, "You must download the latest version". Ok-download. Install. Reboot. Ran MSN, "You must download the latest version". Ok-download. Install. Reboot. Ad nauseum - don't you just love Microsoft for their incompetence? Went to Yahoo site. Download. Run. Done. I'm listening to the radio now. Enough - this is a Blitz site! Frank I sent an email to your private address. |
| ||
| Bouncer's A* Here's my a* function ... might give you ideas how to construct yours. It's a node graph based and it uses heap to really speed it up. Becky Rose A* 3D games usually use 2D pathfinding because at the end of the day, tanks dont fly, if you see what i'm getting at. The point is doing a game in 3D need not complicate your path finding, you can treat it just like 2D. You're better off writting the pathfinding yourself so that you understand it enough to make it work well for your game, but there's no harm in doing so by learning from existing code examples/libraries. Path finding is one of the harder things to implement in a game which is why I try to solve it relatively early in the programs development cycle. Better to grin and bear it early than to put it off and never face it. I usually make my path finding functions in a seperate program using the games actual data but shown onscreen as a 2D map - it helps me tweak the algorythm. This is a modified A* routine which is quite good for searching routes out of a large heightmap based terrain. You can make extra "blocked" areas for trees & houses simply by painting the colour red(255). You'll need to change the heightmap file loaded before this sample will run - I last used this for my Paradise Island project so it's trying to load the heightmap from that... |
| ||
| Binary Decision Tree Source. Ideal for AI Control and Bot Dialog Interfaces. |
| ||
| If you want to create a really versatile AI engine, you might consider using script-like AI files. For example, this is an AI file from the robot waitress in Lego Starwars:
state Base {
Conditions {
}
Actions {
DontPush
CanOpenDoors
SetTaggable "FALSE"
SetState "ChooseMode"
}
}
state Update {
Conditions {
}
Actions {
SetTableLocator
GoToLocator
Idle "5"
SetState "Update"
}
}
state ChooseMode {
Conditions {
if Random < 0.7 goto GoToTable
if PreviousResult < 10 goto SetCounterLocator
}
Actions {
}
}
state GoToTable {
Conditions {
if GotLocator == 0 goto ChooseMode
}
Actions {
SetTableLocator
GoToLocator "WALK"
Idle "5"
SetState "ChooseMode"
}
}
state SetCounterLocator {
Conditions {
if GotLocator == 1 goto GoToCounter
if GotLocator == 0 goto GoToTable
}
Actions {
SetCounterLocator
}
}
state GoToCounter {
Conditions {
if GotLocator == 0 goto GoToTable
}
Actions {
GoToLocator "WALK"
SetState "WaitForDexter"
}
}
state WaitForDexter {
Conditions {
if GotLocator == 0 goto GoToTable
if LocatorRange > 0.1 goto GoToCounter
}
Actions {
CallDexter
Idle "1"
SetState "WaitForDexter"
}
}
state MainRoom_BeingServed {
Conditions {
if Message "ServingCustomer" == 0 goto GoToTable
}
Actions {
FaceCharacter "character=Dexter"
}
}
As you can see, this style is versatile and easy to use. Each state can contain actions and conditions. Conditions redirect program flow to different AI states. Actions are executed every "loop". A script like this could easily be loaded directly into some state-machine system, or compiled and loaded into a VM. |
   |