Author : Filipe Medeiros
Page : << Previous 8 Next >>
we want to put our item, we just set our item's `next' pointer to that item's `next' pointer, and then set that item's `next' pointer to point at the new item.
The disadvantages of linked list are memory usage and inefficiency in finding an item by number. The memory usage is greater because of all the pointers in the list, and because it's generally a large number of small chunks (in particular, as of writing this, djgpp's `malloc' function has a minimum block size of 4096 bytes). Finding an item by number is inefficient because we need to step through the whole list from the beginning to get to it, whereas in a sequential list we can jump straight to it with a single addition.
As always, which system you'll want to use will depend upon what you're using it for.
It often simplifies code if the first item in a linked list is a "dummy" item (sometimes referred to as the "list head"), whose data has no meaning. The reason for this is that it makes storing empty lists simpler -- they become lists with only one item, the dummy.
I suggest at this point that you have a look at `src/5.3/ii/single' for some examples of adding, removing and finding items in linked lists.
I think you'll probably see now why linked lists can be so useful -- we can create as many shapes as we like, whenever we like, and just add them to the list in an efficient way. We don't really care what their number is in the list; if we need to refer to specific items in the list for some reason we can use a pointer to that item, rather than its ordinal number.
5.3.2.2 Doubly linked lists
Assuming you understood the preceeding section, this should be fairly easy to grasp. In the singly linked list above, each node had one pointer to the next node in the list. In a doubly linked list, each node has two pointers -- one to the next item in the list, and one to the *previous* item in the list.
struct dllnode { struct dllnode *next; struct dllnode *prev; int number; } *ptr;
Now it is possible to find the whole list given a pointer to any node in it. It is still often useful to make the first node in the list (the one with `prev == NULL') a dummy node whose data is not used, for the same reason as above. It can act as a "handle" to the list -- something to hold on to, that will always be part of the list. The other nodes will be added and removed at times, remember; the head element is the only one that's guarranteed to be there all the time.
One advantage of using a doubly linked list is that you can remove a node from a list without needing to know which list it is in. Another advantage is that if an entity in the list needs to scan the list it can do so without needing to be given a pointer to the head of the list. Also, given any item in the list you can add an item on either side without needing to scan the list. Doubly linked lists are generally easier (and more efficient) to maintain, but they do of course have a little more overhead.
`src/5.3/ii/double' is an example of a doubly linked list and routines to manipulate it.
5.3.2.3 Circularly linked lists
Again, if you've understood linked lists so far this shouldn't be too hard. In our singly linked list we had the `next' pointer of the last node set to NULL, marking the end of the list. In a circularly linked list, the last node's `next' pointer points back to the start of the list -- so there isn't really a last node. Think of it as a ring of nodes, each pointing to the next.
If the circular list is doubly linked, the first node's `prev' pointer points to the last node.
Empty circular lists are also a problem; using a dummy node is useful here too, but you must remember to skip over it when you're stepping around the loop. Alternatively you can make your pointer to the list NULL when it's completely empty, but you still have to make special cases.
Circular lists are useful for different things to linear linked lists; in game programming you generally want to do something to everything in the list once per game cycle, and for this purpose a linear linked lists is often better. I mentioned circular lists here for completeness, and because they're not very different to linear lists. For an example, see `src/5.3/ii/circular'.
5.3.2.4 Using linked lists
Try modifying your shape moving program, making it put the shapes into a linked list and animate them from there. You could also make it add a new shape every 100 game cycles, or make it delete one. See `src/5.3/ii/using' for an example of this.
This method of putting all game entities into a linked list and animating them is very useful. You can put the player's ship/man/being in there too; if the player's character is similar in action to the enemies then this can work well.
5.4 Object Oriented Programming
An input device is anything you use to give information to the computer. The standard PC only has a keyboard, although most have mice and many have joysticks. In a way I suppose a disk drive is also a sort of input device, as are microphones, scanners, and modems, but they're not generally good things to use to control a game.
We'll look at each of the main three in detail, then consider abstracting our input system. Finally we'll look at different ways to use the input information.
6.1 Keyboard input
6.1.1 Why the standard PC keyboard routines are useless
The standard PC keyboard interface is almost, but not quite, entirely useless as a game control device. There are several reasons for this; firstly, whether you hold a key down or just tap it the game would only see one keypress for a certain period (usually a quarter of a second). Then if you held the key down it would fill the buffer with many keypresses, which means the game might still be reading them after you let go of the key. Also, if you hold one key down and tap another, the first key will seem to have been released.
These combine to make the standard PC keyboard routines useless for controlling action games. Thankfully Allegro provides a set of much better routines.
6.1.2 Allegro's keyboard routines
In your Allegro programs, you should call `install_keyboard()' during initialisation. Then you can use Allegro's keyboard routines.
Most importantly, there is an array of chars called `key' which has one element for each key on the keyboard. It is indexed by keyboard scancode (not ASCII code), and you can get the scancode for a key using the `KEY_*' constants defined in `allegro.h'. For example, to see whether the space bar is currently down, test whether `key[KEY_SPACE]' is non-zero. You probably remember seeing the input routine earlier on checking whether or not the ESC key was pressed.
After installing Allegro's keyboard handler, the BIOS routines won't work anymore. This includes conio's `getch', stdio's `getchar', `gets', `scanf' and anything else using stdin. Allegro provides a replacement for `getch' called `readkey', which waits for a key to be pressed and returns an integer composed of its keyboard scancode and the ASCII value; to split it up, you must do something like this:
int value, scancode, ascii; value = readkey(); scancode = value >> 8; ascii = value & 0xff;
See the Allegro documentation for more information.
6.1.3 Moving something using the keyboard
There are several ways in which the game objects can respond to the input. For now we will make the objects move at a constant speed in the direction the user indicates. We'll discuss other models later on.
So, what we require is something like this:
if (key[KEY_LEFT]) x--; /* if the user is pressing left arrow, go left */
if (key[KEY_RIGHT]) x++; /* same for right */
if (key[KEY_UP]) y--; /* same for up; note that y _decreases_ to go up */
if (key[KEY_DOWN]) y++; /* and for down y _increases_ */
where `x' and `y' are the object's X and Y coordinates.
Try modifying the moving (single) circle program to allow the user to move it around. Try to fit your program into the suggested structure, too. Example program `src/6.2/iii' demonstrates this.
6.1.4 Letting the user choose which keys to use
Unfortunately, since the PC keyboard wasn't really designed as a game control device, it cannot track all the keys independently. It doesn't even come close. There are certain
Page : << Previous 8 Next >>