This course is the fourth course in the specialization about learning how to develop video games using the C# programming language and the Unity game engine on Windows or Mac. Why use C# and Unity instead of some other language and game engine? Well, C# is a really good language for learning how to program and then programming professionally. Also, the Unity game engine is very popular with indie game developers; Unity games were downloaded 16,000,000,000 times in 2016! Finally, C# is one of the programming languages you can use in the Unity environment. This course assumes you have the prerequisite knowledge from the previous three courses in the specialization. You should make sure you have that knowledge, either by taking those previous courses or from personal experience, before tackling this course. The required prerequisite knowledge is listed in the "Who this class is for" section below. Throughout this course you'll build on your foundational C# and Unity knowledge by developing more robust games with better object-oriented designs using various data structures and design patterns. Data structures and design patterns are both general programming and software architecture topics that span all software, not just games. Although we'll discuss these ideas in the game domain, they also apply if you're writing a web app in ASP.NET, building a tool using WinForms, or any other software you decide to build. Module 1: Explore a Dynamic Array data structure and learn the basics of algorithm analysis Module 2: Learn about and use the common Linked List and Graph data structures Module 3: Learn about and use several additional data structures: Stacks, Queues, and Trees Module 4: Learn why design patterns are so useful and discover a number of design patterns useful in game development Module 5: Complete final peer review
Unordered ints
Loading...
From the course by University of Colorado System
Data Structures and Design Patterns for Game Developers
7 ratings
University of Colorado System
7 ratings
Course 4 of 5 in the Specialization C# Programming for Unity Game Development
From the lesson
Dynamic Arrays and Algorithm Analysis
Meet the Instructors
Dr. Tim "Dr. T" ChamillardAssociate Professor
Computer Science
In this lecture, we'll learn how to implement an UnorderedDynamicArray to hold ints.
So, that means that we will grow the array as we need to as we add elements to the array,
but we don't care what order those elements appear in in the array.
We'll start by looking at the parent class for
both the Unordered and Ordered IntDynamicArrays.
So, this is an abstract class
because there are some methods in here that we don't know how to implement.
We'll leave that to our child classes.
We have an ExpandMultiplyFactor.
So, once the underlying array here gets full,
we're going to need to expand it.
And the way we'll expand it is,
we will double its size each time we need to expand it.
And that has been shown historically to be a reasonable approach.
We don't want to just add one to the array size every time because then,
we'll end up having to expand it all the time,
but we don't want to multiply it by a hundred either
because we can end up wasting lots of memory that way.
So, doubling the size each time we need to expand it is reasonable.
Speaking of that underlying array, here it is.
So, it's an integer array called Items,
and we're going to keep track of the Count as well,
because in this array,
some of those items will be valid and some of those items won't be valid.
And so, we need a way to keep track of which ones are valid and which ones aren't,
and Count is the way we're going to do that.
Here's our constructor.
We create a new array with four elements,
and we set Count to zero because at this point,
the array is empty.
The only property we provide for the array is Count.
And here are those methods that we don't know how to implement here in the parent class.
So, we've made all three of them abstract.
So, we're going to be able to add something to our IntDynamicArray,
we're going to be able to remove something from our IntDynamicArray,
and we'll be able to find the IndexOf a particular item in our IntDynamicArray.
And each of the child classes,
both of the child classes,
will implement those three methods in different ways.
Clearing out the array is a very straightforward operation.
All we have to do is set Count to zero which indicates
that there are now no valid elements in the array.
Of course, the elements in the array are holding whatever values they used to hold,
but we don't care.
There's always bits in elements of an array,
and we're indicating that none of those values are valid at this point.
The last public method we have in the parent class is
the ToString method that just converts
the IntDynamicArray to a string of comma-separated values.
We do have one protected method and that protected method expands the array.
So, if in fact the array is full and we want to add an item to it,
we need to make it bigger.
Now, we know that once we've created an array object,
we can't actually increase the size of that array object.
So, here's what we do.
We create a new array called newItems,
and we make the size of the new array the size of
the current array multiplied by that multiply factor.
So now, we have newItems,
an array of twice as many elements as the current array of items.
Now, we copy everything from the items array into the newItems array.
And finally, we change items to refer to newItems.
So, because arrays is a reference site,
we can just change the reference for our items
array to be a reference to that new array that we created.
In the old array, we'll just get garbage collected
whenever the garbage collector decides to collect the garbage.
That's it for the parent class.
Let's look at the child class for an Unordered IntDynamicArray.
As you can see, I've made it to child class of that parent class.
I have a constructor that just calls the constructor for the parent class.
And here are those abstract methods.
So, the first one is adding an item to the Unordered IntDynamicArray.
The first thing we have to check for is whether or not we need to expand the array.
So, if Count, the number of valid values in the array,
is equal to the size of the array,
that means we don't have any room to add another item to the array,
so we need to expand it,
which is what we do here.
Now that we've expanded the array,
we add the item at items count,
and we increment Count,
and you should go do an in-video quiz about this.
Okay, so Count keeps track of the IndexOf the next place we're going to add an item.
So, if you think about this,
if Count is four,
then the indices for the valid elements in the array are zero,
one, two, and three.
So, items count is the next available slot for a valid item when we need to add one.
It's also useful that Count happens to be the number of elements in the array as well.
So, we're using Count for double duty here and that's really handy.
The next method is to remove an element from the array.
So, the first thing we do is look for it,
and we'll talk about the IndexOf method soon,
but if IndexOf returns negative one for the itemLocation,
then the item we were looking for doesn't appear in the array,
so we return false.
Because we haven't removed it,
it wasn't there in the first place.
Otherwise, itemLocation is the location of the element that we're removing,
so we can just copy the element at the very end of
the valid elements in the array into that location instead,
and then we decrement Count and return true.
The last method in the Unordered IntDynamicArray class is IndexOf.
So, we need to look for a particular item.
This is pretty straightforward because this is an Unordered IntDynamicArray.
The only thing we can do is start at the beginning and look for
the item we're looking for until we either find it or we get to the end.
So, this for loop locks that array.
And if in fact the current element we're looking at is the item we're looking for,
then we return i,
the IndexOf that element that we just found.
And if we look through all of the valid elements in the array and we don't find the item,
then we return negative one because we didn't find it in the array.
So, that is
both the parent class IntDynamicArray and the child class Unordered IntDynamicArray
for an Unordered array that can grow as we need it to.
To recap, in this lecture,
we learned how we can implement a parent class for a Dynamic Array of ints,
and we also saw how we could implement the child class for in an UnorderedDynamicArray.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
