A side-scrolling platformer written in C using raylib. It is based on Hayao Miyazaki's movie of the same title. The goal of the game is for Kiki to collect loaves of bread and deliver them with her broom, while avoiding the enemies of each level.
This is a project for the course of Data Structures and Software Principles of Spring 2021. Aside from implementing the Abstract Data Types required for this course, my aim was to use the low-level abilities and high degree of flexibility that C can offer to optimize performance, which is crucial for game design.
- To compile and execute in the terminal, from the directory Source-Code/game run:
$ make
$ ./kiki
- On a Mac you can simply double-click on the
Kiki's Delivery Service.app
and the game will begin. You can also play the game online here.
In addition to the data structures I used for the game, all the abstract data types I implemented for the purposes of this course can be found in the modules folder and are the following.
- In ADTVector.c is my implementation of ADT Vector using ADT Map. I simply use the key of the map to position the element in the vector. Given that the map functions are executed in O(logn), it follows that
insert()
,vector_set_at()
,remove_last()
are done in O(logn) time, as well as all the other functions for traversal.
- In ADTDeque.c is my implementation of ADT Deque using ADT Map. When I insert at the beginning of the queue, I subtract 1 from the first element for the position. This is because the key can have negative numbers and there is no need to move the elements, by keeping these relative positions. As with my Vector implementation, in the Deque as well apart from
deque_find()
all the other functions have O(logn) complexity.
- In ADTDeque.c is my implementation of ADT Deque using Dynamic Array. I keep a pointer to the first element head and to the last tail. This way there is no need to move the elements when a new one is inserted or removed. Thus, the complexity compared to using ADTMap is better for
insert
andremove
since they are done in O(1) time, as well asset_at
,get_at
since we have random access to the elements, as opposed to before when this was done in O(logn) time. But the implementation with dynamic array lags, when doing resizes which take O(n) time.
- In ADTVector.c is my implementation of ADT Vector using Real-Time Dynamic Array. Here, I added
array_X
that holds the old array until all elements have been copied. This way I can achieve O(1) complexity even for resizes. Also, to keep the complexity at O(1) forset_at
andget_at
, I keep theposition_X
of the last copied element.
-
In ADTSet.c is my implementation of ADT Set using BST. To provide random-access I use a counter for each node of the number of nodes on the left subtree. These "weights" are adjusted when an element is inserted on the left hand side, through the path this element followed with the function
set_fix_weights
.Set_fix_weights_reverse
works in the same way for remove. -
These functions have complexity at most O(h) since they follow the same path down the tree, as the insert or remove. For
set_get_at
I use theleft_weight
counters and keep the position of the minimum element of the tree. So here too complexity is at most O(h), as inset_set_at
, that works in a similar way.
-
In ADTSet.c is my implementation of an AVL Tree using separate chaining, but inserting in an ADT Set instead of a List. I modified the order of the elements to be based on the key instead of the value. Both are stored in the
set_node
, while the other functions are inserted as they are except where adaptation was needed such as in insert, remove and find. In the map I keep the table of pointer buckets in sets which I initialize as null and only when I insert an element in this position I create the corresponding set. I also changed the load factor to 0.9. -
The complexity of the insert is O(n) when we need to rehash, but this is rarely done, so amortized time is O(1). For the search with this implementation, the amortized time is O(1) and going directly to the bucket where the key is located to find the element, the complexity improves from O(n) of the classic implementation to O(logn), because of the AVL tree.
-
In ADTGraph.c is my implementation where I used the Map from Hash Table. The vertex_node struct contains a vertex with a map of the vertices adjacent to it (i.e. edges). I also added add_the_edge which adds these vertices to this node map when the graph is updated with a new edge. If two vertices are not connected by an edge, I chose not to have them at all in the
vertex_pairs
map of the graph (instead of having them with INT_MAX) to save space. I can find these from the other map. -
In
graph_shortest_path_lengths()
I simply create a matrix and with a variation of the Floyd-Warshall algorithm, I find in each cell the optimal path between the edges. Since the graph is undirected, the matrix is symmetric. So, based on the same convention that I followed in thevertex_pairs
map the edges appear once (that is, not both (1,2) and (2,1)) and there is no need to go trough the whole matrix, but only half, the lower "triangle". -
In
graph_shortest_path_nexts()
I use the same algorithm, but I keep both edges. I also have an additional matrix so that when I find a better path, I can save that node instead. In ADTGraph_test.c I have a fairly exhaustive test for the subcases of insert, remove and for the two algorithms.
-
In kikistate.c is the implementation of the state of the game using an ADT Set, instead of an ADT Vector, for the objects of the game. This way it is faster on the system and allows for the game to never drop below 60fps.
-
The
state_update()
function deals with the movement of the character and enemies, as well as with collisions with objects. To makestate_objects()
faster, instead of searching for all the objects of the set, I create an object with coordinates x_to and I find with the use ofset_find_eq_or_greater()
the next object in the set. -
The structure of the game is in kiki.c, where I create a state and by calling
interface_init()
the window is created with the screen_width and height given in kiki_interface.h. There the images from theassets
folder load and by usingstate_objects()
withdraw texture()
they are displayed in the window. -
For the animations I used stop-frames from the movie and with the functions
DrawTextureRec()
,GetFrameTime()
and a modulo operation calculated which frames to use so that they appear in motion during gameplay.