Jump to content
  • Advertisement
  • 06/28/00 01:57 PM
    Sign in to follow this  

    Understanding Data Structures Part 1 : Linked Lists

    General and Gameplay Programming

    khawk
    • Posted By khawk

    June 29, 2000

    This series is actually something I started back when I was part of the Sweet.Oblivion staff, but then some things happened and I was no longer able to complete it. So now, after finally retrieving copies of the original articles, I am going to make a second attempt at a series of articles that cover step-by-step the design, construction, and implementation of the most common data structures used in software development today.

    I will start off the series by briefly introducing basic pointer concepts as well as giving an introduction to our first data structure, linked lists. I will then begin to explore more advanced data structures including, but not limited to stacks, queues, binary trees, AVL trees, splay trees, B-trees, hashes, various types of priority queues (aka heaps), graphs, and quite possibly some topics regarding algorithm analysis and the design of several algorithms that utilize these data structures. I will also make an effort to explain how each structure might be used in your game development.

    The compiler of choice for this series is Microsoft Visual C++ 6, and both C and C++ syntax will be used throughout. Also, since my example programs are to be very simple and to the point, all of the programs will be using the console application setup - basically an MS-DOS program.

    Now that you have the general idea of this series, let me warn you that this series does have a chance of not being completed, but considering the general lack of good tutorials and documents covering this material, I'll do my best to follow through with each part. I just cannot guarantee that between my personal life, work on GameDev.net, and other issues that may arise in the future, that I will be able to complete it. So with this in mind, let's get on with the show.

    Getting Started

    Before we can begin discussing any dynamic data structure, we need to verify that you have a solid background on basic pointer operations.

    A Quick Explanation

    Dynamic memory is allocated from an area of memory known as the heap - a finite supply of memory that can be accessed by the programmer. It is possible to deplete all available memory from the stack or heap, since both are of some definite size that is machine-dependent. A program uses stack memory when a function is called, and this memory is released when the function exits. Allocation and deallocation of stack memory is therefore automatic. This is, however, not the case for heap memory, and the programmer must carefully manage the allocation and deallocation of heap memory.

    You could write a set of functions that can help you keep track of how much heap memory you have allocated and how much is being used in the program, but that is beyond the scope of this article and would be a good topic for another article. Such a system could be used in resource management.

    Allocating Memory

    To use the memory allocation functions, must be included. Requesting memory from the heap is accomplished through the malloc() function, which is defined by:

    void *malloc(size_t size);
    The malloc() function returns a generic pointer to a chunk of memory containing size bytes. Remember that you must typecast the generic pointer returned by malloc() to the type of the pointer variable that is being allocated. If the heap is full, and no memory is available for allocation, malloc() returns NULL.
     
    Other functions include calloc() (also used for memory allocation of an array) and realloc() (used to increase or decrease the size of a chunk of memory previously allocated). For our purposes, we will use malloc() and free(), which frees the memory that has been allocated for the pointer that is passed as free()'s parameter.

    Using Pointers

    Now let's get into some real implementation. Pointers are declared and dereferenced using an asterisk; the variable itself, without the asterisk, refers to the actual address of the first byte of the allocated memory. Remember, pointers contain as their value an address to another variable. The dereferenced pointer actually points to the value of a variable held in memory at the address indicated by the pointer. The & character (the address of operator) is used to determine the address of a variable.

    Consider this fragment of code:

     

     

    int i, *ptr1, *ptr2; // integer and 2 pointers to integers
    i = 11; // get space for one integer and assign a value
    
    ptr1 = (int *)malloc(sizeof(int)); // note the typecast to integer
    *ptr1 = 43; // Use already allocated space
    
    ptr2 = &i;
    printf("i, *ptr1, and *ptr2 = %d, %d, %d\n", i, *ptr1, *ptr2);

    This code outputs:

    i, *ptr1, and *ptr2 = 11, 43, 11

    Let's run through the code very quickly. The first line declares one integer variable, and two pointers to integers. The second line assigns the value of 11 to integer variable i. Line three allocates memory for integer pointer ptr1. The fourth line assigns the value of 43 to the memory location that has been allocated by ptr1. Line five then sets the integer pointer ptr2's address to the memory location occupied by integer variable i. The last line then prints out the values of integer variable i, and then the values being held in the memory locations pointed to by ptr1 and ptr2.

    If you have trouble understanding that, be sure to read over it several times, or look through a C/C++ book or tutorial on pointers. You need to have a solid understanding of pointers before moving on from this point in the series.

    The Linked List

    Now that you understand basic pointer concepts, you may be asking yourself, "What is this linked list thing?" Well, a linked list is a dynamic data structure consisting of records (called nodes) that hold data and are "'linked" to each other by a method determined by the programmer. The most common linking method is through pointers (addresses), such that each record contains the address of the next node in the list in addition to the record's regular data. The first node in the list, called the head, is used as the list's key identifier.

    You must always keep track of the head of the list. Why? Because it is the starting point that will be used later to retrieve the information that you have stored in the list. Lose the head, and you have lost the entry point to the entire list, particularly in our implementation here of the singly linked list. A list expands and shrinks (hence dynamic data structure) as data is added and deleted, allowing the list to accommodate an arbitrary number of elements. Compare this concept to the allocation of an array, which remains the same size during its lifetime. Figure 1.1 shows a visual example of a singly linked list, which we will be discussing throughout this article.

    fig11.gif

    A linked list is a linear data structure. All operations on the list must begin by accessing the first node on the list, then the second node, then the third node, etc. Compared to arrays, this sequential access can be a significant performance drawback. Arrays can be accessed randomly - ever hear of the binary search algorithm? A linked list node can only be accessed after all preceding nodes have been accessed; this results in slower searching algorithms. There are, however, ways around this by manipulating and modifying the structure of the basic linked list that has been described here. We will explore these in a later part of the series.

    The main advantage of linked lists is their dynamic nature. A list can grow to be quite big with dynamic allocation. New nodes can be added in between existing nodes with a few simple pointer manipulations, and deletions may be performed with a call to free() and some pointer redirection.

    Some of the operations that we will be covering on the basic linked list include:

     

     

    • List initialization
    • Search
    • Create a new node
    • Node insertion
    • Node deletion
    • List traversal

    Linked List Node Design

    Now we will discuss the design of the node that can be used in your linked list implementations. The data placed inside a node is dependent upon the application of the list. For instance, let's say that you would like to use a linked list to keep track of the enemy ships that are currently alive and flying around in your space shooter. There are several ways to represent enemy ships with your nodes, but for the sake of simplicity, we will let each node hold the x and y coordinate of the ship on the screen.

    In this example, we will create a struct to package the data.

    typedef struct node
    {
      int x, y; // x and y coordinate
      struct node *next; // pointer ("link") to the next node
    } node_t;

    There we have our basic node structure with the type defined as node_t. Note that you specify struct node *next; because it is a pointer to an incomplete type. The following code demonstrates how we can use this type to declare our variables.

    node_t nodeRec; 			// a single node
    node_t *head; 				// head node of a linked list
    typedef node_t *node_ptr; 	// create a node pointer type
    node_ptr head; 				// head node of a linked list

    The first declaration, node_t nodeRec, declares a variable of the node structure. You can't really use this for your linked lists.

    The second declaration, node_t *head, is what we're looking for. This declares a node pointer that we will use for the head of the linked list.

    The third and fourth declarations are fairly self-explanatory. They create a new pointer type that allows for better code readability, and then declare the head of the linked list using this new pointer type.

    Also keep in mind that the second and fourth lines are equivalent.

    In Figure 1.2, you can see the visual representation of a single node. We will use this representation throughout the series for all the nodes in all the data structures we explore. The node has a data area, where all the node's information is stored, as well as a link area, where the links to other nodes are defined.

    fig12.gif

    When designing nodes, keep in mind that nodes have a data portion and a link portion. You can put any type of data that you want in the data portion, including pointers, structs, classes, or the more common ordinal types. However, for the link portion of the node, you must only create variables that will be used as links to other nodes. Here in the basic design of the linked list node, we created a single link that links to the next node in the list. In future articles, we will expand on this idea and add more links for more complex data structures.

    In the meantime however, we need to discuss some of the basic operations that you can perform on linked lists.

    Node Allocation

    List nodes are created on demand. When data needs to be inserted, a new list node must be allocated to hold it. The malloc() function presented earlier is the basis for this allocation. The statement

    newPtr = (node_ptr)malloc(sizeof(node_t));

    or

    newPtr = (node_t*)malloc(sizeof(node_t));

    allocates our new node. Assuming that malloc() does not return NULL, we may now begin to assign the data portion of our node with values. Here's a quick example, using the coordinate node defined earlier:

    newPtr->x = 10;

    Now that we have the basis for allocating nodes, we create a function that will encapsulate all of the node allocation functionality into one block of code.

    node_t* Allocate()
    {
      node_t *newNode; // our new node
    
      // request memory for our node
      newNode = (node_t*)malloc(sizeof(node_t));
    
      // error checking
      if (newNode == NULL)
      	printf("Error: Unable to allocate new node.\n");
      else
      	newNode->next = NULL; // allocation succeeded, set the next link to NULL
    
      return newNode;
    }

    There we have our basic node allocation function. We use this function like so:

    node_t *myNode = Allocate();

    Despite the function Allocate() printing out an error message if the pointer is NULL, we should still verify that myNode is not NULL before trying to use it. Should this be the case, you may now use the data portion of the node and fill it with values.

    Initialization

    Initialization of a linked list is very quick and easy. We simply assign the value of NULL to the head of the list. This function only needs to be called once, and some of you may choose to not even bother. However, for the sake of this article, we will use it.

    void Initialize(node_t **ptr)
    {
    	*ptr = NULL;
    }

    Using the definition of head given earlier, you would call this function as

    Initialize(&head);

    Node Insertion - Unsorted

    We will now cover how to insert freshly allocated nodes into a linked list. Let's take a step back for a moment and consider insertion into an array. When using an array, you would typically add data to the end of the array, unless the data was sorted, in which case you would insert the data using some other method.

    We could do the same for an unsorted linked list, but this would require finding the last node because only the next to last node "knows" where the last node is located in memory. However, the head of the linked list points to the first node in the list, so a new node can be inserted at the front of the list without any extra work. You can see the steps of inserting three nodes into a linked list in Figure 1.3.
     

    fig13.gif


    And now the code:

    void InsertFront(node_t **head, node_t newRecord)
    {
      node_t* newNode = Allocate();
    
      if (newNode == NULL)
      {
        printf("Error: Not enough memory to allocate node.\n");
        return;
      }
    
      // fill the node with data
      newNode->id = newRecord.id;
    
      // insert at the front of the list
      newNode->next = *head;
    
      // move the head of the list to the new node
      *head = newNode;
    }

    To try to sum up this function in English: a new node is allocated and its data is filled; the new node's next field is set to point to the head node; the head is then reset to point to the new node. This function also works if the list is empty (*head = NULL) since we want the list to be NULL-terminated.

    Linked List Traversal

    In order to access each node in the list for data processing, we need to create a function that will traverse the list. There are several different uses for list traversal, including printing, searching, data manipulation, etc. Regardless of the use, you must traverse your list in order to really do anything useful with this data structure.

    In this example, we will create a function called DisplayList that will display the x and y coordinates of every "enemy" in our list.

    void DisplayList(node_t *head)
    {
      node_t *current; // our current node (position)
    
      // begin at the head of the list
      current = head;
    
      // loop until done
      while (current != NULL)
      {
        printf("ID = %d\n", current->id);
        current = current->next;
      }
    }

    Figure 1.4 shows the visualization for list traversal. As you can see, we move the current pointer through each node of the list until it reaches the NULL link at the end.

    fig14.gif

    Searching

    Searching a linked list is very much like the traversal algorithm just described. The only real difference is that as you go to each node in the list, you compare the data in the node to the "key" data that you are searching for. In this example, I will show you the algorithm using an entire node record as the "key", but keep in mind that this is not the only way to accomplish the search. I leave the other avenues of exploration to you.

    First, let's see how to search the linked list visually by looking at Figure 1.5.

    fig15.gif


    As you can see, searching is in fact almost the same as traversing the list. In the code, the only real difference is an extra conditional statement for comparing the key node data with the current node's data that will force the traversal loop to exit should the statement be true. Take a look at the function Find, which returns a pointer to a node. If Find returns NULL, then no matches were found.

    Keep in mind that this is a linear search, and that the linear search tends to be slow. This is the only way we can search this particular data structure because of the nature of the links. You can do more advanced searches on linked lists by adding more links and changing the nature of the linked list overall. We will get into that in a later article. In the meantime, here's the Find code:

    node_t *Find(node_t *head, node_t keyRecord)
    {
      node_t *current;
      bool found;
    
      current = head;
      found = false;
    
      while ((current != NULL) && (!found))
      {
        if (current->id == keyRecord.id)
        	found = true;
        else
        	current = current->next;
      }
    
      return current;
    }

    Node Deletion

    We're getting close to the end now, as it's time to talk about node deletion. Node deletion is a little bit different compared to the other linked list functions in that you must think of all the special cases that may come up. If you don't think of every special case, you might end up with severe memory leaks, crashes, or in the not-so-bad case, just a program that refuses to delete the desired node.

    For all of the dynamic data structures we discuss in this series, we will need to go through and determine all the cases that will come up when deleting nodes for the data structure we discuss. So let's begin by determining the cases involved in deleting nodes from a linked list.

    To start off, let's discuss the simplest case: deletion of a node in the middle of the list. Let's say we already know what data we want to delete, and we put it in a key node. The first thing we need to do is find the pointer to that node. To accomplish that, we use the Find function that we just created and call the found node current. The next thing we need to do is find the node that links to the node that was just found, which we will call previous. From here, we can now bypass the link to the current node by changing the previous node's link to point to the current node's link. This will "skip" the current node in the linked list chain, but we have not lost this memory since we still have the current pointer. Now that the linked list is intact, we can free the memory used by the current pointer. Take a look at Figure 1.6 to see how this is done.

    fig16.gif

    Now we need to think about another potentially hazardous case of node deletion: the desired node is the first node in the list, but not the only node. In a case like this, all we need to do is set current to the head node, and then move the head pointer to the next node in the list. From there, we just free the current node pointer. Take a look at Figure 1.7 for a better idea.

    fig17.gif

    That's it. There are no more cases for deletion in a singly linked list. You do, however, need to put a verification that the desired node was in fact found, or you could run into some access violation problems.

    Here is our delete function:

     
    void DeleteNode(node_t **head, node_t keyRecord)
    {
      node_t *delNode;// node to delete
      node_t *previous;// node before the deleted node
    
      // find our node to delete
      delNode = Find(*head, keyRecord);
    
      // if desired record is not in the list, exit the function
      if (delNode == NULL)
      {
        printf("Record not found.\n");
        return;
      }
    
      if (delNode == *head)
      {
        // first node in the list, but not the only node
        // move the head to the second node in the list
        *head = delNode->next;
        free((void*)delNode);
      }
      else
      {
        // any other case
        previous = *head;
    
        // search through the list for the node before our deleted node
        while (previous->next != delNode)
        {
        previous = previous->next;
        }
    
        // link the previous node to the node after our deleted node
        previous->next = delNode->next;
    
        if (delNode != NULL)
        {
          free((void*)delNode);// free the memory
          delNode = NULL;
        }
      }
    }

    End Of File

    That concludes our "brief" introduction to the singly linked list. This particular data structure forms the basis for all of the data structures that we are going to discuss throughout the rest of the series.

    Now that we've gone through the important functions involving linked lists, next time we will discuss some of the abstract data types that can be derived and implemented using the base singly linked list. I will also briefly cover some derivations of singly linked lists such as circular linked lists, doubly linked lists, and a few other methods that you might want to experiment with on your own.

     

     



      Report Article
    Sign in to follow this  


    User Feedback


    There are no comments to display.



    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

  • Advertisement
  • Game Developer Survey

    completed-task.png

    We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a $15 incentive for your time and insights. Click here to start!

    Take me to the survey!

  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Advertisement
  • Popular Now

  • Similar Content

    • By GameDev.net
      Lerp( a, b, t ) = value InvLerp( a, b, value ) = t  
      lerp returns a blend between a and b, based on a fraction t inverse lerp returns a fraction t, based on a value between a and b  

       
      Use case! 🔊
      Say you want to control audio source volume based on distance
      at 10 meters, you want volume 1 at 20 meters, you want volume 0 Then the volume is then given by
      volume = InvLerp( 20, 10, distance )  

       
      If you've ever used photoshop's levels tool, then you've used both lerp and inverse lerp! 🎨
      The input values use inverse lerp, the output values use lerp!

       
      When used with images, inverse lerp can be used to increase value contrast! for example, here's a selfie before and after an inverse lerp💖
       
       
      Also, note that some Lerp/InvLerp functions also extrapolate (such as in shaders), while others clamp the values within your given range (such as Unity's Mathf.Lerp/InverseLerp functions) 
      Make sure you clamp unless you want to extrapolate 📈
       
      Here's an interesting use case!
      An inv lerp where a and b are colors and the value parameter is the depth of this water, you can achieve hue-shifting for a color elimination effect by depth🌊
      water.mp4
       
      Addendum - another useful function is Remap!
      Remap takes a value within a given input range into a given output range, which is basically a combined inverse lerp and lerp!
      Here's the code for all three!
      (Also, none of these are clamped - they can all extrapolate)

       
      Enjoyed this quick lesson?  Check out Freya's work via the following social platforms:
      💖 Patreon ❱ https://patreon.com/acegikmo
      📺 Twitch ❱ https://twitch.tv/acegikmo
      🎥 YouTube ❱ https://youtube.com/c/acegikmo
      🐦 Twitter ❱ https://twitter.com/FreyaHolmer
      💬 Discord ❱ https://discord.gg/v5VWuga
      🌸 Instagram ❱ https://instagram.com/freya_holmer
       
      Want to read more about Lerp?  Freya posted a thread here:
       
      Adapted from the original Twitter thread with kind permission of the original author.
      Further reading on GameDev.net: A Brief Introduction to Lerp, by Matt DesLauriers
    • By gustavo rincones
      Hi, this is my first forum and I want to do it: quick way to calculate the square root in c ++ with floating data types. These types of functions are very useful to gain some CPU time, especially when used continuously. I will show you 3 similar functions and indicate the advantages and disadvantages of each of them. The last of these three functions was written by me. If you notice that the writing is a bit out of grammar, it is because I do not speak English and I am using a support tool. My native language is Spanish. Well, let's start:

      The First method is very famous was used in the video game quake III arena and you can find a reference in Wikipedia as: :https://en.wikipedia.org/wiki/Fast_inverse_square_root.
       
      The Function was optimized for improvements in computing times.
      float sqrt1(const float &n) { static union{int i; float f;} u; u.i = 0x5F375A86 - (*(int*)&n >> 1); return (int(3) - n * u.f * u.f) * n * u.f * 0.5f; }  
      -Advantages:
      * When Root of 0 is calculated the function returns 0.
      * The convergence of the function is acceptable enough for games.
      * It generates very good times.
      * The Reciprocal of the root can be calculated by removing the second “n” from the third line. According to the property of: 1 / sqrt (n) * n = sqrt (n).
      -Disadvantages:
      * Convergence decreases when the root to be calculated is very large.
       
      The second method is not as famous as the first. But it does the same function calculate the root.
      float sqrt2(const float& n) { union {int i; float f;} u; u.i = 0x1FB5AD00 + (*(int*)&n >> 1); u.f = n / u.f + u.f; return n / u.f + u.f * 0.25f; }  
      -Advantages:
      * The convergence of the function is high enough to be used in applications other than games.
      -Disadvantages:
      * Computing times are much larger.
      * The square root of “0” is a number very close to “0” but never “0”.
      * The division operation is the bottleneck in this function. because the division operation is more expensive than the other arithmetic operations of Arithmetic Logic Units (ALU).
       
      The third method takes certain characteristics of the two previous methods.
      float sqrt3(const float& n) { static union {int i; float f;} u; u.i = 0x2035AD0C + (*(int*)&n >> 1); return n / u.f + u.f * 0.25f; }  
      Advantages:
      * The convergence of the function is greater than that of the first method.
      * Generates times equal to or greater than the first method.
      Disadvantages:
      * The square root of “0” is a number very close to “0” but never “0”.
       
       
      The 3 previous methods have something in common.
      They are based on the definition of the Newton-Raphson Method. according to the function of the square root > f (x) = x ^ 2 - s.
       
      well thanks to you for reading my forum.
      well thanks to you for reading my forum.
    • By bzt
      Hi,
      I was looking for a way to effectively interpolate between skeletons represented by list of bones with position vector + orientation quaternion pairs. To my surprise, I couldn't find any good solution, not to my taste that is. I can't use NLERP because I need a general solution, and NLERP is only good for small distance interpolations. SLERP would be perfect, but I couldn't find a decent implementation, only slow ones, so I spent a lot of time looking at game engines and quaternion libraries and reading academic articles on the topic. Finally, I decided to collect my findings and write my own optimized version of SLERP, which focuses on performance over precision, and which I now would like to share with you.
      Optimized cross-platform SLERP
      I've started from the well known formula, as implemented by most C++ libraries, and used all the tricks I could find on the net. Then I took it to the next level, and made some more adjustments on my own speeding up a little bit more. Finally I ended up with two solutions:
      1. one that is cross-platfrom, ANSI C solution that is easily embeddable in C++ and compatible with any C / C++ quaternion class (provided their data can be seen as 4 floats), very simple, very minimal. Use it freely if you want, MIT licensed
      2. a SIMD version, which I had to leave half-ready, because my compiler and Intel disagree on what intrinsics should be provided for SSE, moreover the compiler does not work the way its documentation say it should :-( Shit happens. I would only recommend this for experimental purposes, also MIT licensed
      Both versions are simpler and much faster than any implementations I could find, designed to be called in a loop several times. The only dependency they have is lib math (acosf, sinf). The SIMD version is half-ready, but even in this form it's almost 1.5 as fast as the other one, especially if you call it in a loop with memory prefetch on the quaternions.
      If I made any mistake, miscalculated or mistyped something, let me know. If anybody has an idea how to overcome that intrinsics blockade I have, that would be appreciated very much, because I can clearly see the path how to make the code several times faster, only if I could get rid of the library calls. I also plan to create an ARM NEON port once I have that.
      Cheers,
      bzt
    • By Ey-Lord
      Hello everyone

       
      I am here to gather your opinion, remarks, ideas or any constructive criticism you may have about what I am going to present. Don’t be shy!


       
      A bit of background:

      I am working alone on an indy web-based game, a simulation of RPG (idle game) where the player controls a group of 4 characters that he can sent into battle and that will fight automatically based on some AI preference that are similar to the FF 12 system (but more complex / powerful). He then earns some experience and resources that he can use to improve his unit’s gear, talents and skills. He has a lot of control on what skills his characters will use and how/when.


       
      What brings me here today:

      The AI of Monsters. I have the AI settings for players covered (basically a bunch of if/then/and/or/else settings that he can combine and order so that his units will act as he intends in battle). I’ve been working on the AI of monsters for quite some time, made a long break and came back recently to it.


       
      Short description of the battle system:

      No movement involved. Battle is fully automated. Players setup its units AI settings before battle and monsters are controlled by a separate AI. This is a 4v4 battle, like FF7 with some kind of ATB and any time a unit fill its ATB, it can play and the then the next unit who will fill it will play, etc. The player is completely free of his playstyle and may create very offensive group or very defensive ones. 4 healers or 4 tanks is completely possible.

      The battle system is very complex and allows for very varied and sometimes unusual strategies, like killing your own allies to proc an “on death buff” that will be devastating for the opponent.


       
      What I want for my AI?

      It needs to be fun to fight against and challenging. Ideally, I would like an AI as smart as possible (not omniscient but thinking as a human would). I know that a super-smart AI is not always the best way to make a game fun or challenging but in the context of my game, this is the result I want to achieve. It may seem unfair to have the AI try to kill your squishy while your tank is standing right there but my class design gives the tools to players to counter that so it’s not an issue (tanks are not purely aggro based for example). I want players to always be challenged by AI moves and that they must carefully think about their strategy because if they leave a big hole in it, I want the AI to exploit it.

      In practice, it means a few requirements:

      No dumb decision / do not fall into obvious player’s traps Exploit obvious flaws of the opponent Act in coordination when appropriate with other units Able to find who should be their focus in the player’s team (some notion of threat) Find the best move to use and if there is some kind of combo possible, use it

      These requirements are harder to meet than it looks. The issue is the sheer number of different mechanisms and strategies available to players and to monsters as well. For example, there are many cases where killing or attacking a player unit might be detrimental (units that return damages or that gain power when you hit then for example).


       
      What I have tried before?

      I have tried or at least reviewed many different AI concepts so far.

      -          A simple copy of my player’s AI system (hierarchical if/then/else). It was easy to script as I already have the UI in place for players so I can quickly define a basic AI for any new monster’s group. The main drawbacks are that it needs to be written for every monster group, it does not allow smart targeting and cannot find the best target or the best skill to use. It will also make dumbs decision as the targeting options cannot assess threats at all.

                I’ve rules out planners since for purely selecting the best pair of (skill, target), they do not seem to match my needs.           (H)FSM or BT does not seems to match my needs as monsters do not have states / transition condition that can lead to something useful for me.        I’ve ruled out aNNs as they might, with proper training, be able to find the best action at a given time but it’s very tedious to implement and will not solve my need of finding combo or coordinating with other units very well. (plus, let’s be honest, I’d be a bit out of my depth to program them)           I have spent an extensive period of time trying with tree searches. Mainly: monte-carlo with random sampling and came to the conclusion that due to the complexity of my battle system, it is excessively costly to compute any kind of reliable data this way.
      -        My current AI system is a version of my first one (the same as the players) but with access to some “smarter” targeting function that in theory allow to choose the best target. These functions work by gathering data for thousands of simulated fights during the AI time to play (1 second). It’s a first step to find the best target but not very accurate (lots of big flaws that can be exploited by players) and it is very time consuming and that is something I’m trying to get away from. I do not want to use 100% of the players CPU as I do now.


       
      What is my latest idea?

      I started to study more in-depth the Utility theory as described by Dave Marks (I read his book and watched his GDC AI lectures as well). I liked the idea. I like that I can start on something relatively simple and add more considerations as things progress to handle more and more situations. While my work began as something very close to utility theory, it evolved a bit afterward. Here is what I plan on doing to compute a unit’s best course of action:


       
      A – Score every of its move (each move is a pair [skill, target]).

      B – Chose the move according to a selection strategy (highest score, weighted random, random amongst the top scores… lots of different selection algorithm can be used there).


       
      So far, easy, right? Let’s dig deeper into our first phase of scoring (A), which is the hard part. For all the damage or healing skills:


      Step 1: The final scoring of the move [skill,target] will be function of the a “Survival” scoring for the player team and for the enemy team. An example of this relationship could be: Adding all the survival scores of each unit in Team A and divide the result by the addition of all the survival scores for each unit in team B.

      Step 2: The survival score of each unit will be its Health after the move we are evaluating, divided by the total damage per turn that we estimate other units can deal to her (minus the total heal it ca receive). [This a step where we can process damage and heal over time as well]

      Step 3: This damage per turn estimation will be, initially, the sum for every unit in battle of the damage or heal per second it can deal to that unit. For example: If I’m alone vs 2 bad guy that can deal 1 dmg/turn and if I can deal 1 heal/turn, the damage per turn estimation against me will be 2-1 = 1. [This is not optimal since we are counting the damage of each unit once per enemy unit but it’s a start]

      Step 4: To compute the DPS or HPS of each unit, we review the unit’s skills and compute their output against the unit we want to evaluate it against. From that, we construct a skill sequence to maximize the damage output and once we got the optimal skill sequence, we can compute its DPS or HPS output and pass it along for Step 3.


       
      It might seem like a lot of work, since, in a world with only damage or healing skills, the DPS or HPS sequence of each unit will be the same in every situation and as such only the damage done or healing done by the skill evaluated would be enough. But…


       
      The tricky part comes from buffs and debuffs. If we use the above algorithm, (de)buffs that changes the damage or healing someone does or receive will be evaluated correctly as it will change the damage or heal per second output of units and it would affect the survival score and the final scoring. That is why I chose to include DPS and HPS computations for each unit for each move.


       
      This is all fine until we consider (de)buffs that changes the power of other (de)buffs. Like: I cast a buff that double the length of all my future buffs. My algorithm can’t evaluate it correctly. It’s a situation that will be common enough in my game and I want my AI to deal with it. Note: there are more complex situations where a unit could buff a buff that buffs a buff that buff a buff [….] that will end-up buffing a damage or healing skills, but those cases will not be addressed as they will hopefully be rare and too cumbersome to compute anyway.


       
      So, my goal is to score properly buffs that: 

            Buffs the damage or healing output of someone           Buffs that buffs a skill that does the above

       
      L    Long story short of how I am doing that. I’m using my initial algorithm but while also estimating damage or healing per second change for each dps or hps sequence.To do that I’m evaluating every move of the unit (or every unit in case of AoE but lets keep it simple with single target) that is targeted by the buff. So, we are switching PoV here compared to the initial unit we are evaluating (unless the move evaluated is buffing itself)

      -          I’m doing the above in 2 situations:

      o   A : After a cast of the buff skill I’m evaluating

      o   B : Without the cast of the buff, just like if it was that unit’s turn to play

      -          Using a sort of min/max approach: if the unit targeted by the buff is an ally, we will take the best branch of our tree in A and compare it with the same branch (pair [skill,target]) in B. If the unit targeted by the buff is an enemy, we want to lower their maximum score and will select the tree branch that does that in A to also compare it with the same branch in B.

      -          The information we extract here are DPS or HPS delta for each sequence of DPS/HPS for each unit vs each other unit.

      -          Then, we go back to our steps 1 to 5 and compute our scoring for the move (buff) while using our new dps/hps deltas to get better and more accurate dps/hps sequence for units affected by the buff.


       
      This is basically it. I’ve ran a manual version of the algorithm in 2 different battle settings to test it and see if it gave good results. It worked. Not flawlessly but it worked. Lots of cases will still require tweak and additions to the basic idea but I think its promising. (taunts and CCs are not easy to deal with but it’s manageable)


       
      What I like is that I can add more considerations later (as in the utility theory) like: resource cost, general unit strategy (cleave or focus), behavior (careful, lunatic, reckless). While this will still be a bit time consuming it should be a good order of magnitude faster than my current AI. It also does not prevent me from adding hardcoded AI move if I want to “script” more some monsters. Debugging and tweaking might be a bit painful though, especially when fights will involve lots of skills & stats but that’s an issue that most AI for my game would likely have anyway.


       
      To come back with my initial goals:

              No dumb decision / do not fall into obvious player’s traps
      o   Not perfect but it should choose the best target whenever possible

                 Exploit obvious flaws of the opponent
      o   Same as above

              Act in coordination when appropriate with other units
      o   This can be done simply by adding weight to some targets or computing moves for all units of a group before deciding which one to take (for example to take the best move vs a specific unit, on average)

             Able to find who should be their focus in the player’s team (some notion of threat)
      o   It will naturally focus the unit who is the easiest to kill and debuff or CC the ones that deal the more heal/damage. But, to better solve this, we will need to add other considerations to the AI scoring process, It should not be *too* hard    

            Find the best move to use and if there is some kind of combo possible, use it
      o   Combo are very often in the form of buff/debuff setup before an actual damaging or healing skills and my AI can compute up to a 3 moves combo (buff > buff > skill that dmg or heal) which should cover most cases.


       
      I’m quite happy with my initial tests. I’m not going to be coding it now. My goal was to reflect on the subject on paper and try to see if designing my AI would be a roadblock or not for my project. There are a few other area I want to design and take time to really think about before getting back to my project full time. I’d love to hear your toughs and feedbacks about my AI ideas. Do you see huge roadblocks I’m missing? Does it sound ok to you?

      If you read that far…. thank you and I can"t wait to hear from you guys😊

    • By Sword7
      I googled for terrain collisions but found only some sources about flat worlds.   I want collision detection for spherical terrain worlds.   I have "3D Engine Design for Virtual Globe" book but it did not mention any algorithms about collision detection for landing, rolling, walking, crashing, etc...   Does anyone have any good sources for spherical terrain collision detection?
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!