• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Norman Barrows

AI speedups for running game in accelerated time

28 posts in this topic

Is it possible to simplify your rendering - as that might now be eating significant time in the speed up mode (to get to your 5400X)

 

Is the game already threaded with the graphics on a seperate thread and working on a once (interval) copied snapshot of the game situation so the simulation only need to wait briefly for that atomic copy  (should be fast and maybe only copy the render related data if that is faster)

 

It sounds like you are running exactly the same simulation calculations which will result in exactly the same results as if it was run at normal speed (and it doesnt sound like its abstractable to simplify the simulation calculations)

 

What kind of sensory scanning do your objects do  (adjacents only ??  a box search ? something more comples)

 

How is the edge of map endcase handled.  There are some tricks to get rid of the  XY tests needed when doing object sensor scanning which can simplify the objects calculation some.  (I had a guy doing A* change to have a boundry edge of cell blocked status  to eliminate the x<0 x>maxx y<0 y>maxy  that had to be tested on all the adjacency tests   and for a box check it is setting the XY loop limits once instead of inside the loops

 

 

---

 

Depending on the complexity of the behaviors here  - the old method called the Big Switch inside the main game turn object loop which flattens out

the program alot  can eliminate a great deal of processing overhead.   Of course it depends on how your simulation is run whether that would actually be multiple processing loops per turn   (sensor+decision phase, action phase, action resolution phase).

 

But if you dont have multiturn interactions bewteen objects (and have resolution of all actions in the current turn)  the logic can usually fit and not be too obscured in one loop routine employing the Big Switch

Edited by wodinoneeye
0

Share this post


Link to post
Share on other sites

Is it possible to simplify your rendering - as that might now be eating significant time in the speed up mode (to get to your 5400X)
 
Is the game already threaded with the graphics on a seperate thread and working on a once (interval) copied snapshot of the game situation so the simulation only need to wait briefly for that atomic copy  (should be fast and maybe only copy the render related data if that is faster)

 

the game is currently single threaded. one loop for drawscreen, doinput, and move_everything. the game is framerate limited to 15 frames per second. i know, 15 fps seems slow. and it is. its the slowest you can go, and still get sufficiently responsive input and smooth enough animation. so its the speed at which you'll have the maximum possible number of milliseconds (66 2/3) per frame to draw stuff and simulate stuff. and lord knows, none of us has enough frame time. even cheating to get 66ms vs 33 ms at 30fps, i'm still pressed for what i want to usually accomplish.

 

multi threading has not yet been considered due to keeping system requirements to a minimum for maximum compatibility.  right now a directx 9 capable pc is the only system requirement - not even QueryPerformanceCounter is a requirement (yet).

 

it doesn't get a screen dump and then just display that. it draws the scene. once per game minute  - once every 900 iterations of the main game loop, hence the 900x speed. it does 900 "turns" of input and simulation, then draws a frame. same idea for the 5400x speed, one frame drawn per game hour (once every 5400 main loop iterations). a screen dump would be faster, but then you couldn't watch the world go by in time lapse photography mode like you do now.

 

It sounds like you are running exactly the same simulation calculations which will result in exactly the same results as if it was run at normal speed (and it doesnt sound like its abstractable to simplify the simulation calculations)

 

correct. it turns off the frame rate limiter, allowing the simulation scream at full throttle. then it just draws the screen once every 900 turns, where a "turn" is one iteration of the main game loop, and represents 1/15th of a second of game time.

 

as for an abstraction, that may be possible. i was doing the same thing in another title the other day (a flight sim). any idea how long it takes to fly to a target 1000 miles away in an airship that does 47 mph? <g>. there i was using 100x and 1000x speeds. but it still wasn't fast enough. so i did an approximation. there it was easy, just moving a single target a long way until it gets close to something. just draw the chronometer showing mission time passing. before you know it, that 13 hour flight to target is done, and its time to lower the observation car and bombs away! accelerated time is an absolute must in any simulator. unless its one of those "real time" sims - log in once a day, water your virtual pet kind things.

 

but abstracting the AI would much more difficult here. you have predatory, stand your ground, and maintain distance behaviors all going on at once. and all of those use wandering and flocking as well as targeting and combat behaviors. so approximation of results is much more difficult.

 

in the airship sim, i didn't have to recalculate the density of helium given the altitude and temperature 15 time a second to approximate flying across europe, the way it does when running in real time. all i had to do was move the ship based on current orientation and airspeed, and check for range to targets, then fixup the altitude etc when they dropped back to real time speed. in the caveman sim, an average approximation could be done. IE given some mix of critters, on average who will have eaten whom after some given period of time. but it would not yield the same results as running the simulation in real time with full AI and modeling, the way the airship approximation does.

 

What kind of sensory scanning do your objects do  (adjacents only ??  a box search ? something more comples)

 

there is no chess board like map for targets. so no map based searches such as adjacency or box search apply. targets are stored in a sparse matrix, IE a target list. sensory scanning consists of looping through the target list looking for nearby targets of interest. and nearby means looping through the list again for each target to get range. thus the (O)n^2 (or whatever it crunches out to) kinda thing going on.

 

How is the edge of map endcase handled.  There are some tricks to get rid of the  XY tests needed when doing object sensor scanning which can simplify the objects calculation some.  (I had a guy doing A* change to have a boundry edge of cell blocked status  to eliminate the x<0 x>maxx y<0 y>maxy  that had to be tested on all the adjacency tests   and for a box check it is setting the XY loop limits once instead of inside the loops

 

not an issue yet. environments are mostly outdoors with just trees or big rocks to navigate around. so no A* yet. just bang and turn, no avoidance or anything. works ok for now. they still kill you plenty quick (you die a LOT in this game!) <g>. i've already gone though the code and pulled all non-essentials out of the loops. about all i found was one lookup call to terrain_visual_range() that returns the max visual range based on intervening vegetation coverage (you can see far in the desert and not far in the jungle).

 

Depending on the complexity of the behaviors here  - the old method called the Big Switch inside the main game turn object loop which flattens out
the program alot  can eliminate a great deal of processing overhead.   Of course it depends on how your simulation is run whether that would actually be multiple processing loops per turn   (sensor+decision phase, action phase, action resolution phase).

 

you mean something like this?

 

 

void move_animals()
{
int a;
for (a=0; a<maxanimals; a++)
    {
    if (!animal[a].active) continue;
    if (!animal[a].alive) continue;
    if (animal[a].suprised) continue;
    setstate(a);
    runstate(a);
    }
}
 
 
void setstate(int a)
{
int t;
t=animal[a].type;
if (animal[a].defend_location) defend_location_setstate(a);
else if (animal[a].state==FRIENDLY) friendly_setstate(a);
else if (animal[a].state==HOSTILE) hostile_setstate(a);
else if (animaltype[t].AI==ATTACK_AI) attack_setstate(a);
else if (animaltype[t].AI==MAINTAIN_DISTANCE_AI) maintain_distance_setstate(a);
else if (animaltype[t].AI==DEFEND_AI) defend_setstate(a);
else all_others_setstate(a);
}
 
0

Share this post


Link to post
Share on other sites

The 'big switch' Ive used before usually has a persistant state of behavior for an object where It doenst recalcumate it scoarse stance as frequently as it does incremental moves

 

Thus for your irt might be every one in 10 'turns' it recalculated the objects general situation and may change its stance and within that stance ther are particular incremental actions  at a specific level.

 

 

The object then has a switch/case statement it jumps to for its current state most of the time instead of running all the possible logic.

 

That also allows state specific logic to be run and special cases or logic with adjusted coefficient to match that 'stance' (state)

 

Smarter objects may reevaluate their state more frequently  (or when woken up by important external effects)

 

 

Thus the first phase is figuring out of objects need a state change and if so calculating it

 

and the second is running the state specific logic for the incremental turns

 

SOme obejcts actions take several turns and they are locked into that action for a certain count and they dont need to do any complex situation analysis because they are already committed to the action

 

 

 

Another phasing can be where you decide what all objects have to do using the data from the last turns situation  (its frozen)  and then the next phase is using that decision to carry out its actions generating THIS turns results and situation data.    Otherwise the situation data would be changes andreflect turn+1 for some objects and not for others.  Depending on game mechanics and increment sizes that may not be needed)

 

---

 

 

for the Grid map way of deciding adjacent objects  you can do it for Space Partitioning  with arbitrarily sized grid cells  If your N for the N^2 comparisons  is sufficiently large  (and interaction range means you usually interact with a substantially smaller subset )  then the overhea of inserting and removing object markers on a space partitioning grid can increase efficiency of finding which objects interact (when adjacent/close enough to each other.)

 

This can be particularly tru when you have alot of passive object that dont more or rarely move (an they dont need to have their grid positions checked and adjusted much)

 

Whenever you move you check if an object is still in the grid cell it previously was and if changed its removed from the old cell and added into the new current cell  (link list)     If the cells are many (fine grained)  the link lists are short  if the cellsa are large (in relation to how far objects move per turn) then they dont change cells  very frequently  negating possibly longer link lists (objects that move the most are near the head of the link list so they have lower  removal times (insert at head is in constant time)

 

 

Generally you want to size the grid cells to have be larger than the maximum interaction range so you only have to check membership in the objects immediate cell and its 8 neighbors (if 2D mapping)   3x3 cells to check ...    It Can be done checking  further out 5x5..7x7..9x9 etc..  cells using a xy loop traversal  (if needed when some objects have very long interaction ranges)

 

Example - a 10x10 full space partitioning grid of map with garanteed interaction range of less than 1/10th width of map  you only have to check  3x3=9  out of 100 total cells  for each object  (and you can sometimes do optimizations - gang all the objects in that center cell together to test against the 9 candidate 'adjacent' cells - lots of walking of link lists...)

 

 

 

For large maps and large counts of objects that method can cut down the N^2  interaction testing significantly  (I had maps with huge numbers of largely inactive objects (10s of thousand) and a few significant objects that moved alot

0

Share this post


Link to post
Share on other sites

Thus for your irt might be every one in 10 'turns' it recalculated the objects general situation and may change its stance and within that stance ther are particular incremental actions  at a specific level.

 

This  would be the "select target" every 5 seconds, and the "randomly change AI state" every 5 or 10 seconds, when critters are just mulling about (stand, flock, and wander behaviors).

The object then has a switch/case statement it jumps to for its current state most of the time instead of running all the possible logic.

 

You mean like this...

 

void runstate(int a)

 

{
//show_hostile_info(a);
if (animal[a].collision_recovery) 
    {
    move_collision_recovery(a);
    return;
    }
switch(animal[a].AIstate)
    {
    case 0: // stand
            if (animaltype[animal[a].type].avian)
                {
                if ( animal[a].y > heightmap(animal[a].mx,animal[a].mz,animal[a].x,animal[a].z) ) land(a);
                else standani(a);
                } 
            else standani(a);
            break;
    case 1: // wander
            steer_animal3(a,0);
            moveRun(a,0);
            walkani(a);
            break;
    case 2: // run away
            steer_animal3(a,1);
            moveRun(a,1);
            walkani(a);
            do_animal_atk(a);
            break;
    case 3: // flock
            steer_animal3(a,0);
            moveRun(a,0);
            walkani(a);
            break;
    case 4:    // attack
    case 11:   // predator hunt 
            if (frame % 15 == a) calc_heading_to_target(a);
            set_rng(a);                                          // calc rng to tgt
            if (animaltype[animal[a].type].avian) run_avian_attack_AI(a);
            else 
                {
                steer_animal3(a,0);
                new_moveAtk(a,0);
                walkani(a);
                do_animal_atk(a);
                }
            break;
    case 5: new_eatkill(a,animal[a].butchered); break;
    case 6: new_move_cornered_animal(a); break;
    case 7: run_defend_location_attack(a); break;
//  case 8: not used
    case 9: new_moveto_home(a); break;
    case 10:    // friendly & all others attack
                if (frame % 15 == a) calc_heading_to_target(a);
                set_rng(a);                                          // calc rng to tgt
                new_steer_animal(a);     
                new_move_animal(a);
                do_animal_atk(a);
                break;
    }
}
 

 

for the Grid map way of deciding adjacent objects  you can do it for Space Partitioning  with arbitrarily sized grid cells  If your N for the N^2 comparisons  is sufficiently large  (and interaction range means you usually interact with a substantially smaller subset )  then the overhea of inserting and removing object markers on a space partitioning grid can increase efficiency of finding which objects interact (when adjacent/close enough to each other.)

 

 

yes, right now, almost all data in the game is stored in sparse matrices (IE lists of whats on the map and where, but no map grid). easy on the memory requirements, but slow to search. environments for collision check purposes can be tight and complex, as the terrain is randomly generated at the start of a new game. so for collision checks, a moving critter might look through a list of trees, a list of fruit trees, a list of rocks, a list of PCs, a list of caves and rockshelters, a list of critters, and the world map (the only grid data structure) for flags indicating other collidables such as tarpits, volcanoes, and huts. a change of data representation to a method that is more conducive to spatial searching may be called for. but at the moment, its really not that bad. I did test it with and without critters, and i'm looking at 4 games hours in 4 seconds with no critters active, and 4 game hours in 7 seconds with critters active. its rare that the player will accelerate time for more than 8 game hours at a time. imagine playing the sims, and the game is running at 1 game hour per second. in no time at all, your poor little sim would be dead from starvation, etc.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0