Grid based game

[skydereign]

I'm just going to say, linked lists are very handy, and I do tend to use them, but a lot of the time games don't need them. There are easier, and relatively efficient ways of handling it that are easier for newer programmers to understand. Usually there is a natural progression as you learn C, jumping to structs and linked lists is a rather large leap from having trouble with arrays. But, for the longest time on these forums, arrays were more of a mystery to the average user, so I see that you are pushing for change but do keep in mind that there are some users that won't be able to make that leap.

[foleyjo]

So Sky in your opinion would you say I should try to learn and understand Evans code for this? Or do you think there is a different method I should work with before making the Leap?

[skydereign]

Well, I would need to know more about what you are doing, but generally speaking this doesn't sound like linked lists will make it much easier. In fact this sounds like pretty simple array handling will do what you want. Where if you were handling linked lists, the construction of the list wouldn't be as nice as setting the array. Is your only concern that you want to make the size of the grid changeable? Because as long as you know the height and width of the array, then finding the adjacent squares is pretty easy.

[foleyjo]

I feel like I'm being a pain with this thread. I hope it ends up being helpful to others too.

I'm trying not to go in to too much detail because I don't want people to do too much of the work for me.

I'll give a brief run down of what needs to happen

Player selects square in grid.
Activity happens on square.
If a particular action happens on the square it sends an event to all adjacent squares (not diagnoal) to start these squares performing an activity

The reasons I want to use changeable grid sizes is so that I can concentrate on getting my game working on a small grid. This will help me for testing. Then I will increase the grid size to an enjoyable level.

I am also considering adding different grid patterns to make things more enjoyable but that won't be until the main game works.

[foleyjo]

Evan I really don't understand what I'm doing with the code you gave me. I don't know where to put it in game-editor and keep getting error when I try different locations

[EvanBlack]

You put that code into global script. They are declarations to functions and structs. All global declarations go into global script.

[foleyjo]

Code: Select all

int Position = 4; // Start at the middle square

// Create all the square structures

Square TopLeftSquare, TopMiddleSquare, TopRightSquare,
      CenterLeftSquare, CenterMiddleSquare, CenterRightSquare,
      BottomLeftSquare, BottomMiddleSquare, BottomRightSquare;


// Put all the squares into an array for later use.

Square grid[9] = { TopLeftSquare, TopMiddleSquare, TopRightSquare,
                  CenterLeftSquare, CenterMiddleSquare, CenterRightSquare,
                  BottomLeftSquare, BottomMiddleSquare, BottomRightSquare };

Keeps telling me this section is illgal

[EvanBlack]

Code: Select all

Square *grid[9] = { &TopLeftSquare, &TopMiddleSquare, &TopRightSquare,
                  &CenterLeftSquare, &CenterMiddleSquare, &CenterRightSquare,
                  &BottomLeftSquare, &BottomMiddleSquare, &BottomRightSquare };


This is how it should have been written sorry. Use this instead, its a pointer to all the squares on the grid. Also, CenterLeftSquare and some other square variables are misspelled. Just which the a and u so it spells square instead of sqaure. Its in the next section of code.

You shouldn't get any errors then.

[skydereign]

Well, not sure if you need this, but it is pretty simple. It actually doesn't use an array currently, as from what you have said so far, it isn't necessary. All you need are the clones.

So here is a function that returns the cloneindex of the clone next to a position (x,y). You pass it the position, and a direction (0 is right, 1 is up, 2 is left, 3 is down). It uses two ints, num_columns and num_rows, to determine the size of the grid. You can also write a function that takes a cloneindex and determines an (x,y) on the grid, so you can use the cloneindex of the actor to then use for the get_cindex function. Didn't include it as you said you wanted to do as much as you can by yourself.

Code: Select all

int num_columns = 3;
int num_rows = 3;

int
get_cindex (int gx, int gy, int dir)
{
  int x_offset = 0;
  int y_offset = 0;

  switch(dir)
    {
    case 0: // right
      x_offset=(gx+1 < num_columns);
      break;

    case 1: // up
      y_offset=-(gy-1 >= 0);
      break;

    case 2: // left
      x_offset=-(gx-1 >= 0);
      break;

    case 3: // down
      y_offset=(gy+1 < num_rows);
      break;
    }

  if(x_offset+y_offset != 0) // square is valid (would return 0 if square isn't valid)
    {
      // gets the cloneindex of position (gx,gy)
      return ((gy+y_offset)*num_columns + (gx+x_offset));
    }
  return -1; // does not exist
}

[foleyjo]

Going to go through all the code you guys have given me and see what I can do with it.

While I was waiting on replys I continued with the code I was originally working with.

I got it sort of working.
It adds counters to the grid in the correct locations except for the top right and bottom left.
If anyone would like to take a look and let me know where I went wrong I would really appreciate it.

[foleyjo]

(Anyone sick of me yet ? )

Evan I put the code in and as I did it I started to understand what was going on.

Howevvvveeerrr I'm unsure how I now draw the grid on screen.

I made a control actor and in the create actor event put
AllocateMemoryForGrid();
CreateGrid();

Do I need an actor in a square shape? I think I do but unsure how to reference it.

[skydereign]

The problem with the system is that you are using negative positions in the grid. One problem it creates is that modulus doesn't work how you'd expect with negative numbers. For grid position -2, you expect -2%3 to be 1, but gE says it is -2. The reason is that gE (really C to be more general) doesn't have the rule that the dividend must be positive, therefore the divisor (for negative numbers) is always one less than it should be. Of course, your system seems to rely on that form of modulus half the time. I would suggest raising the grid to not use negative positions, or not to use that system. I'd also be careful when using linked lists for this, as at least the CreateGrid function that is being used doesn't scale nicely (if you wanted it to do that, then you would need to automate it).

[EvanBlack]

Ok, using a linked list for grid isn't really to draw the grid, but it can be. It use to save positions in a list that describe a square. Use any system you want, the code I given you wasn't exactly for created large grids it was just meant to help teach you understand how it works. There are easier methods that make creating the linked list faster, less lines of code.

Also, I don't use negative numbers when doing coordinates, the reason being because the natural first position on a coordinate map is 0,0. Then continue outward positively. A pixel grid on a computer doesn't use negative, and usually negative numbers represent off the map, or void area.

Using linked list for grids is perfect because you can add more properties to a single element than an array, where in an array you would have to create multiple arrays, they would have to be of set size, or you would have to allocate more memory for the array and do expensive transfers of values to all of your arrays. Both arrays and linked lists require you allocate memory, but the difference being that when you allocate more memory for the new element in the list you don't have to create an array of larger size, then transfer all of the information, then free the old array. Not to mention you would have to do this for every array that has values pertaining to, what could have been, a single element in a linked list.


Also, with arrays you literally need double the memory capacity just to add a single element to the array. Where as a linked list you only need enough memory to hold the new structure you are creating, and if you don't have enough memory for the new structure you know right away, whereas an array system you would have to first try to create every array, test to make sure you have enough memory to create those new arrays.

Example of array system versus linked list system:

Code: Select all


int xValueArray [100];
int yValueArray [100];
char NameArray [100] [27];
Type TypeArray1 [100];
Type TypeArray2 [100];


int CreateNewArrays(int oldSize, int newSize)
{
    int xValueArrayTemp;
    Allocate memory for xValueArrayTemp of newSize;
    check to see if Memory was allocated if not return failed;

    Transfer values from xValueArray to xValueArrayTemp;
    free xValueArray;
    Allocate memory for xValueArray of newSize;
    check to see if Memory was allocated if not try allocating space of oldSize;
    check to see if Memory was allocated if not free xValueArrayTemp, return failed and begin ending game;
    The game must end because there is no array for xValueArray so functions cannot run properly;

    Otherwise:
    Transfer values from xValueArrayTemp to xValueArray;
    Then start the process over for every array;
}


Linked List

Code: Select all

typedef struct MyElement
{
    int x;
    int y;
    char name;
    Type TypeVar1;
    Type TypeVar2;
    struct MyElement * NextElement;
} MyElement;

MyElement * FirstElement;
MyElement * LastElement;

int NewElement(int x, int y, char *name, Type TypeVar1, TypeVar2)
{
     Allocate space for new element
     check to see if space was allocated if not return failed
 
     Set values of the struct

     LastElement->NextElement = NewElement;
     return success
}

void InitializeLinkedList()
{
    Allocate space for FirstElement if failed endgame because if there isn't enough space to create the first item then there isn't a game, we just started.

    LastElement = FirstElement;

    for(number of elements)
    {
        if(!NewElement(variables))
          { end game because there isn't enough memory to run the game}
    }
}


Its easy to use linked lists and they are very useful for doing exactly what you want to do.

Arrays have their use to but for creating grid structures that hold values such as this it just depends on the way you code it. If you are comfortable with using many arrays and aren't going to be resizing them a lot and need fast random access to any position in the grid then arrays can be used for just that. But the problem is arrays require more memory when handling them if not accessed through reference.

I like to use a hybrid Linked List/Array system that allows for random access to the linked list but doesn't require many arrays. You can also use Structs with arrays so you don't have to create multiple arrays for single values such as:

Code: Select all


typedef struct MyElement
{
    int x;
    int y;
    char name;
    Type TypeVar1;
    Type TypeVar2;
} MyElement;

MyElement ElementArray [100];



The issue being if you were to want to resize the array then you would have to still allocate a temporary array of the same size then transfer the values, then free the old array and allocate the space for the new array size. Its a taxing process but can be made also simpler if you just use an array of pointers to the structures rather then having an array of structures themselves.

Code: Select all


typedef struct MyElement
{
    int x;
    int y;
    char name;
    Type TypeVar1;
    Type TypeVar2;
} MyElement;

MyElement * ElementArray [100];



But this process requires that you allocate space for each element of the array and pass the address of the element to the position in the array. This makes resizing the array less taxing and more memory friendly. But you still have to allocate each struct in the array which if you run out of memory then you have to make sure that if your array isn't full that when you are accessing pointers in the array that are null that you don't dereference them.

All these methods are essentially the same.

[skydereign]

Sounds like that was somewhat said towards me. The negative grid position was something that foleyjo was doing in the ged that was posted (foleyjo asked why it wasn't working). So, if you did think I was talking about your system, I wasn't.

As for the linked lists versus arrays, most of that is true, but only in certain cases. There are many cases where linked lists are overkill. Especially from what foleyjo was asking, it doesn't sound like an array is even necessary, just clones. So while linked lists are a beautiful way of handling and organizing large grids, in simple cases like this, why use a grid at all?

I personally only use linked lists if I need something that can scale easily while being able to maintain lots of information. Most of the time, games made with gE won't need anything like that. The only times you would need to worry about memory are when you expect to have a lot of information that changes in size. Otherwise it isn't really more efficient. In fact, if the size of the grid isn't meant to scale, then a 3x3 array, versus a linked list of 9 members, the array is more efficient and compact memory wise. Linked lists are a way of wrapping information, which as you said becomes more convenient when allocating larger lists (grids), instead of trying to realloc several arrays (especially when you want to preserve the data), but if you don't need to wrap the data, then I wouldn't use them.

[EvanBlack]

Sounds like that was somewhat said towards me. The negative grid position was something that foleyjo was doing in the ged that was posted (foleyjo asked why it wasn't working). So, if you did think I was talking about your system, I wasn't.

Wasn't toward you, I was attempting to clearify the uses of them, thanks for adding to the clarity of Arrays and Linked lists. It wasn't my system I was explaining either, I was just also talking about how I handle finding positions in a game and to make it easier. Not using negative positions could just be an easier way of handling positioning of actors. Considering anything under 0 off the world map.

Yes, using Arrays can be more efficient in many ways, not just for the compactness of the array but also because of the linear structure in memory. As compared to a linked list which has its elements scattered through out the entire memory bank, sorted by the cpu algorithms.

As for his game, I meant that he needs to find the best system that works for what he needs done, even if it means creating a new one from scratch.

There are many different ways to handle the situation. Whether it be with Pure Actors, using scripted arrays or linked lists, whether it be multiple arrays, a multi-dimensional array, an array of actors, an array of structures, a linked list of actors, or even linked arrays. There are so many possibilities for the same thing, deciding on which to use could also be a matter of how many times are you going to reuse the same code.

For me, using linked lists with structures and hybriding with arrays gives me exactly what I need to make reusable code that I can put into many different games without changing any of it, the only thing I have to change is the resources such as: Art, Story, Music, and character variables. I am just trying to express that finding the best code for a specific situation can often go beyond what he might need now into what can he reuse later.

Honestly, he could make the game using only actors and probably only event scripting.

I was just trying to show one method of using it that would allow learning of useful tools. Then it seemed that it would be better to clarify both the use of arrays and linked lists. Maybe I didn't give all the information but if you want to learn more about both then use google. It is very useful.

I hope you don't think I am offended by what you are trying to say, I am not trying to offend you. I am just trying to clarify what I was trying to get at by saying to use a linked list. This is all about help and educating, I'm learning too.