Last few years I've been sporadically working on a game engine, in order to give support to some ideas I have about how a game development should be faced. The product in general turn out to be pretty nice but, as I coded it in Java (back then it sounded like a good idea) I ended up realizing that the lovable yet a bit dull single-inheritance approach and the lack of tools like closures eventually leaded me to little uncomfortable design details that made me uneasy.
This was kind of a bummer, because my choice of Java was not arbitrary: I wanted a mature object-oriented language that could be easily deployed and would run in as many hardware platforms as possible and managed it's own damn memory efficiently. Also I wanted to be able to integrate my development tools with mercurial (which I favor before Git for no good reason), some reasonably simple dependency manager and a good, robust IDE.
Making a long and boring story short (and boring) I decided I didn't yet want to part ways with the JVM (wich I'm very fond of) but it was about time to kiss Java goodbye, so now I'm in the process of migrating the whole thing to Scala.
Let me tell you, once you have passed the little Eclipse plug-in glitches it's quite all right! Even so, regardless of my not-so-little experience in booth functional and object oriented programming I had some trouble finding a way of doing things that feels just alright. You know, like a good pair of old slippers, just with partial application and pattern matching.
What do you want me to say? I like the sensation that i'm getting the best out of my code. I know it's a long way to walk, so I figured that writing about interesting cases and the decisions I took and sharing it with the rest of you may lead me to a better understanding, and therefore a better use, of these new tools.
What do you want me to say? I like the sensation that i'm getting the best out of my code. I know it's a long way to walk, so I figured that writing about interesting cases and the decisions I took and sharing it with the rest of you may lead me to a better understanding, and therefore a better use, of these new tools.
Anyway, I recently came up with one of these interesting problems with some nice design difficulties. It goes like this:
As I said I'm working on a game engine, which requires quite a lot of vector algebra and 2D computations. It's not just that many objects in my framework require to maintain a position on the screen (which can be easily represented with an (X,Y) pair); they usually are also in need of similar structures to represent direction versors, area dimensions and other vectorish thingies.
One possibility was to simply use a Scala touple to model a vector. That would have been a simple path (plus they could be instantiated with that nice touple syntactic sugar), but I found touples to be too generic and didn't feel like they would be a proper reification. After all, vectors are some of the objects the engine users would have to manipulate the most, and I would rather give them a nice, well defined interface to do it instead of just two Doubles tied with a bow.
Some may suggest to use the Pimp My Library pattern for this, but there is another catch: I wanted vectors to be mutable (at least those that would be used to represent a position) so the heap won't be saturated every two seconds because of the objects moving around. Don't get me wrong, I'm not a big fan of performance optimization, but in a game engine object's position is constantly changing and my FPS would be very upset if didn't took this one for the team.
Given all this, I decided to start with a classic approach and ended with something like this:
class Vector(var x : Double, var y : Double) extends Cloneable {
override def toString = "(%.1f, %.1f)" format (x, y)
override def clone : Vector = super.clone.asInstanceOf[this.type]
// Immutable operations
def +(v : Vector) = clone += v
def -(v : Vector) = clone -= v
def *(d : Double) = clone *= d
def /(d : Double) = clone /= d
def unary_- = clone * -1
def module = sqrt(x * x + y * y)
def asVersor = clone / module
def distanceTo(p : Vector) = (this - p).module
def squareDistanceTo(p : Vector) = {
val v = (this - p)
v.x * v.x + v.y + v.y
}
// Mutable operations
def set(i : Double, j : Double) = {
x = i
y = j
this
}
def +=(v : Vector) = set (x * v.x, y * v.y)
def *=(d : Double) = set(x * d, y * d)
def -=(v : Vector) = set(x - v.x,y - v.y)
def /=(d : Double) = set(x / d, y / d)
}
Notice how I only included low level operations on this class (no position related code, just plain reusable vector manipulation). I didn't want to overload it's interface, since it was meant to be used for many ends. That leaved me in the need for a place to put my high level positioning related code. As I wanted it to be as reusable as possible and didn't wan't it to be bounded to a specific hierarchy I went for a trait:
I know, that's not much of a movement API, but I'm expecting it to grow soon. Anyway, so far this didn't look so bad: I had my efficient mutable vector and had reified the way of using it as a position in a trait that only requires it's users to provide a position. This could even be nicely done using class parameters on the many classes that would need to be Positioned, so they could be implemented in a short elegant way:
I somehow needed a way to let Positioned manipulate the Vectors in a wider way than the rest of the users, including the class that should receive it as a constructor argument.
After a bit of thinking I remembered C# approach to a similar situation. I figured that, if there where two ways of working with the same object, I should let them be two ways indeed; so I break the Vector class in two: an immutable logic trait and a mutable class extension.
There where a few interesting changes. First of all, the clone implementation was replaced by a copy method that allows the immutable Vector to create a duplicate with a different (X,Y) set. I find this copy method approach much simpler than the Smalltalk's Species pattern and I often prefer it when possible.
MutableVector was implemented as a case class, in order to get free implementations of the equals and hash methods and a constructor that doesn't require the new keyword.
Also, check a little closer the Positionable implementation. Notice how it only exposes immutable Vectors? This prevents any encapsulation break while, at the same time, leaves the door open to the trait's users to treat the position as mutable.
Although this solution solved the mutable/immutable issue, it was still unclear (now that the position was already being provided by the trait) how the Positioned users could be implemented to support instantiation with a parametrized position. Clearly class value arguments could not be used anymore, because they would override Positionable implementation, and I'm not very fond of code like the following:
I would much rather having the initialization code for my objects abstracted into a method, instead of throwed around. Besides, what if I want different ways to initialize my objects? Let's say, I want to create a Ball from another Ball. I won't be able to do so with a this method, because they can only be defined as a single call to another this method.
I found that the best approach to this may be to embrace the use of Scala's companion objects; that is objects that act as the class-side method implementors (pretty much like Java static methods).
As you may be aware, the "apply" message may be invoked by simply evaluating the receiver as if it where a message itself. This (combined with a little tweak on the "beAt" method to make it return the receiver) allows the Ball class to be instantiated like this:
Sweet! We are almost there... The only thing left to do was checking how Scala's singular features could improve the usability of these constructions. This was probably the hardest part because, as I'm relatively new in Scala, I wasn't aware of the whole of it's tools and, those I where, I was not used to applying them. Although, I did knew what details where bothering me: MutableVectors where too verbose to instantiate and some symmetrical operations (like scalar product) where not symmetrical at all.
I found that the answer for almost all of my problems where ussing implicit definitions. What I went after was being able to write a nice looking Touple (you know, something like (12,15)) and let Scala figure out I meant to say a Vector. Also, I wanted to provide an implementation of the *(v : Vector) : Vector method that could be used by Doubles. I ended up doing the following:
I choose to put the implicits in the Vector companion object, so it would be easy to remember where they are. (I'm not sure if this is a good practice or not, though...). Sadly I couldn't find a way to implement a symmetrical equals between Touple and Vector, and this post convinced me it was not gonna happen :(
Even so, this last changes allowed me to write this sort of code:
The complete final code looked like this:
So that's it. I'll try to keep this site updated, posting about other interesting cases as they appear. In the meantime I appreciate any comments or advise about how to improve the code.
See you around,
N.
trait Positioned {
def position : Vector
def x = position.x
def y = position.y
def move(delta : Vector) = position += delta
def beAt(nextPosition : Vector) = position.set(nextPosition.x,nextPosition.y)
}
I know, that's not much of a movement API, but I'm expecting it to grow soon. Anyway, so far this didn't look so bad: I had my efficient mutable vector and had reified the way of using it as a position in a trait that only requires it's users to provide a position. This could even be nicely done using class parameters on the many classes that would need to be Positioned, so they could be implemented in a short elegant way:
class Ball(val position : Vector) extends Positioned {
...
}
val myBall = new Ball(new Vector(12,5))
However, this implementation was far from being good, the main concern being that, despite I wanted to be able to mutate the vector from inside Positioned trait, I didn't want to let that door open for any Ball user. Perhaps it's just me being paranoid, but I prefer to be able to give the Ball control over it's inner state changes. With this implementation the very same val definition that made position available for my trait also made it available for the rest of the world, which felt like an encapsulation rape.I somehow needed a way to let Positioned manipulate the Vectors in a wider way than the rest of the users, including the class that should receive it as a constructor argument.
After a bit of thinking I remembered C# approach to a similar situation. I figured that, if there where two ways of working with the same object, I should let them be two ways indeed; so I break the Vector class in two: an immutable logic trait and a mutable class extension.
trait Vector {
def x : Double
def y : Double
def copy(x : Double = x, y : Double = y) : Vector
def unary_- = this * -1
def +(v : Vector) = copy(x + v.x, y + v.y)
def *(d : Double) = copy(x * d, y * d)
def -(v : Vector) = this + -v
def /(d : Double) = this * (1 / d)
def module = sqrt(x * x + y * y)
def asVersor = clone / module
def distanceTo(p : Vector) = (this - p).module
def squareDistanceTo(p : Vector) = {
val v = (this - p)
v.x * v.x + v.y + v.y
}
override def toString = "(%.1f, %.1f)" format (x, y)
}
case class MutableVector(var x : Double, var y : Double) extends Vector {
def copy(x : Double = x, y : Double = y) = MutableVector(x, y)
def set(i : Double, j : Double) = {
x = i
y = j
this
}
def +=(v : Vector) = set(x * v.x, y * v.y)
def *=(d : Double) = set(x * d, y * d)
def -=(v : Vector) = set(x - v.x, y - v.y)
def /=(d : Double) = set(x / d, y / d)
}
trait Positioned {
protected val _position : MutableVector = MutableVector(0, 0)
def position : Vector = _position
def x = position.x
def y = position.y
def move(delta : Vector) = _position += delta
def beAt(nextPosition : Vector) = _position.set(nextPosition.x, nextPosition.y)
}
There where a few interesting changes. First of all, the clone implementation was replaced by a copy method that allows the immutable Vector to create a duplicate with a different (X,Y) set. I find this copy method approach much simpler than the Smalltalk's Species pattern and I often prefer it when possible.
MutableVector was implemented as a case class, in order to get free implementations of the equals and hash methods and a constructor that doesn't require the new keyword.
Also, check a little closer the Positionable implementation. Notice how it only exposes immutable Vectors? This prevents any encapsulation break while, at the same time, leaves the door open to the trait's users to treat the position as mutable.
Although this solution solved the mutable/immutable issue, it was still unclear (now that the position was already being provided by the trait) how the Positioned users could be implemented to support instantiation with a parametrized position. Clearly class value arguments could not be used anymore, because they would override Positionable implementation, and I'm not very fond of code like the following:
class Ball(initialPosition : Vector) extends Positioned {
beAt(initialPosition)
...
}
I would much rather having the initialization code for my objects abstracted into a method, instead of throwed around. Besides, what if I want different ways to initialize my objects? Let's say, I want to create a Ball from another Ball. I won't be able to do so with a this method, because they can only be defined as a single call to another this method.
I found that the best approach to this may be to embrace the use of Scala's companion objects; that is objects that act as the class-side method implementors (pretty much like Java static methods).
object Ball {
def apply(position : Vector) = new Ball().beAt(position)
}
class Ball extends Positioned {
...
}
As you may be aware, the "apply" message may be invoked by simply evaluating the receiver as if it where a message itself. This (combined with a little tweak on the "beAt" method to make it return the receiver) allows the Ball class to be instantiated like this:
val b = Ball(MutableVector(4,5))
Sweet! We are almost there... The only thing left to do was checking how Scala's singular features could improve the usability of these constructions. This was probably the hardest part because, as I'm relatively new in Scala, I wasn't aware of the whole of it's tools and, those I where, I was not used to applying them. Although, I did knew what details where bothering me: MutableVectors where too verbose to instantiate and some symmetrical operations (like scalar product) where not symmetrical at all.
I found that the answer for almost all of my problems where ussing implicit definitions. What I went after was being able to write a nice looking Touple (you know, something like (12,15)) and let Scala figure out I meant to say a Vector. Also, I wanted to provide an implementation of the *(v : Vector) : Vector method that could be used by Doubles. I ended up doing the following:
object Vector {
implicit def touple_to_vector[T <% Double, U <% Double](t : (T, U)) : Vector = MutableVector(t._1, t._2)
implicit class DoubleVectorExtender(val d : Double) {
def *(v : Vector) = v * d
}
}
I choose to put the implicits in the Vector companion object, so it would be easy to remember where they are. (I'm not sure if this is a good practice or not, though...). Sadly I couldn't find a way to implement a symmetrical equals between Touple and Vector, and this post convinced me it was not gonna happen :(
Even so, this last changes allowed me to write this sort of code:
val myBall = Ball(4,5) 2 * b.position b.move(6,9) MutableVector(4,5) == (4,5) MutableVector(4,5) != (4,6) -(5,7) distanceTo (4,5)I love it! The resulting code is tidy and very expressive and most engine users won't even know MutableVector is there unless they are in the explicit need of a mutable vector. It's certainly quite an improvement from the original versions and much more flexible an reusable than any possible Java implementation.
The complete final code looked like this:
object Vector {
implicit def touple_to_vector[T <% Double, U <% Double](t : (T, U)) : Vector = MutableVector(t._1, t._2)
implicit class DoubleVectorExtender(val d : Double) {
def *(v : Vector) = v * d
}
}
trait Vector {
def x : Double
def y : Double
def copy(x : Double = x, y : Double = y) : Vector
def unary_- = this * -1
def +(v : Vector) = copy(x + v.x, y + v.y)
def *(d : Double) = copy(x * d, y * d)
def -(v : Vector) = this + -v
def /(d : Double) = this * (1 / d)
def asVersor = copy(x, y) / module
def module = sqrt(x * x + y * y)
def distanceTo(v : Vector) = (this - v).module
def squareDistanceTo(p : Vector) = {
val v = (this - p)
v.x * v.x + v.y + v.y
}
override def toString = "(%.1f, %.1f)" format (x, y)
}
case class MutableVector(var x : Double, var y : Double) extends Vector {
def copy(x : Double = x, y : Double = y) = MutableVector(x, y)
def set(i : Double, j : Double) = {
x = i
y = j
this
}
def +=(v : Vector) = set(x * v.x, y * v.y)
def *=(d : Double) = set(x * d, y * d)
def -=(v : Vector) = set(x - v.x, y - v.y)
def /=(d : Double) = set(x / d, y / d)
}
trait Positioned {
protected val _position : MutableVector = MutableVector(0, 0)
def position : Vector = _position
def x = position.x
def y = position.y
def move(delta : Vector) = _position += delta
def beAt(nextPosition : Vector) = {
_position.set(nextPosition.x, nextPosition.y)
this
}
}
object Ball {
def apply(position : Vector) = new Ball().beAt(position)
}
class Ball extends Positioned {
...
}
So that's it. I'll try to keep this site updated, posting about other interesting cases as they appear. In the meantime I appreciate any comments or advise about how to improve the code.
See you around,
N.
No comments:
Post a Comment