Creating an AI Controller - Bezier Curves and More

I've talked a bit here about my coursework for my DirectX module. I also have a project for my AI class, which I've been working on over the past few days.

The Assignment

The assignment is simple: Create a fuzzy logic controller for a racing game that will control the NPC cars. The suggested implementation is extremely simplistic - the road is represented by a line, the car by some simple symbol or sprite, and the line moving left or right represents curves.

Inputs and Outputs

The inputs to the controller are twofold. First, the position of the line relative to the car, negative being on the left, positive on the right, in pixels. Second, the relative velocity of the line with respect to the car, in pixels per second.

The output will be the suggested acceleration for the car in order to bring it closer to the line, in pixels per second per second.

Membership Functions

I've decided to use five membership functions for each input (far right, right, center, left, and far left). For output, I've decided on nine membership functions (extreme right, large right, right, slight right, center, and so on).

For the shapes and locations of these functions, I've created an HTML5 interface which allows several points for the shapes to be adjusted via sliders and text boxes. Internally, all shapes are represented as trapezoids with four points: the left base point, left peak point, right peak point, and right base point. Additionally, each trapezoid has two "curviness" settings, left and right. The idea is that with these six settings, we can create any and all of the common membership function shapes (triangle, trapezoid, curve) and any combination of them, and they are all represented identically within the code. This will allow me to tweak the membership functions easily to tune the controller.

A screenshot of the control panel for modifying the membership functions

This took a bit of doing, but I'm happy to say I've completed it and the interface is really nice.  The most difficult part was the representation of the "curviness" for the sides of the trapezoid. I wanted to keep this simple from a user standpoint, but I wasn't sure what equation to use for the curves and how to constrain the system. After some discussion with an old colleague from my chemical engineering days, Robert Coolman, I determined that a cubic spline function would be appropriate. The native capabilities of the HTML5 canvas led me to investigate the bezier curve. It turned out this was just what I needed - the bezier curve is a spline using one or two control points. Using the demo located on sitepoint.com's excelent tutorial, I was able to visualize exactly what I would use to represent the "curviness". The two control points are located on the same y coordinate as the endpoints. The x coordinate for the control points can range anywhere in between the two x coordinates, but to keep symmetry must be an equal distance from their respective end point. This distance, then, represented the "curviness". I specify some value from 0 to 10, which is then scaled to the space between the two x coordinates.

The next problem, once this was determined, was actually applying the Bezier curve's equation to find a corresponding y coordinate. This is done internally by the HTML5 canvas to draw the curve, but to use the controller I would need to be able to find it on my own. Unfortunately this would require finding the solution to a cubic equation. After some perusal of various articles including Wikipedia's Bezier Curve and Cubic Equation articles, I was able to write a function to find the real cubic root of an equation given the coefficients, and was able to determine those coefficients from the Bezier curve equation and a bit of algebra.

Rules

Given these inputs and outputs, I created a fuzzy associative map in order to ensure each situation was covered under a rule. I also plan to represent the ruleset internally in a similar fashion, to make it possible to procedurally step through the rules, and to even make it possible to tune the rules as needed.

Fuzzy Associative map covering all possible set combinations

Defuzzification

For defuzzification, I plan to keep things simple and use the Center of Maximums method. This should provide fairly accurate results as long as membership functions are mostly symmetrical - for non-symmetrical membership functions, error will be introduced due to the method not accounting for portions of the function below the maximum plateau being uneven. If I have sufficient time I may look into the center of gravity method, but for now it is beyond the scope of my plans.

The Game

The game itself will be coded using the HTML5 Canvas and JavaScript. A line will represent the centre of the road, and a sprite will represent the car. The camera will be centred on the car, but both the car and line can move freely about the game world.

There will be both a defined track (movement of the line defined using pattern movement techniques) and a user controlled track (movement of the line controlled  by the user as described in the assignment sheet).

Second AI Controller: Genetic Algorithms

The assignment also requires a second AI method to be used in addition to Fuzzy Logic. I am interested in genetic algorithms, so I plan to use a genetic algorithm to tune the fuzzy logic controller. I will then compare this result to my manually tuned controller.

Wish List

In addition to the basic features outlined above, I have several advanced features I'd like to add:

• After a track is run, the program should automatically display a summary of the performance of the AI for that course, and several useful graphs and statistics including standard deviation.
• The ability to save membership function settings to file both before and after a track is run would be useful.
• Similarly, the ability to load these membership functions from file would also be useful.
• For the genetic algorithm tuning, it would be great to watch the membership function values change in real time.
• A real-time animation of fuzzy logic operations while AI is running the track could provide insight into AI actions and assist in debugging.

Completion of some of these features could take the project beyond a simple exercise and make it a useful teaching tool for demonstrating fuzzy logic in the future.

Creating a DirectX Scene - This is not the bug you're looking for

I've been working on my DirectX scene over the past few days, primarily cleaning up my code and making it more object oriented. I created an array of models and render them via a loop now. Unfortunately this revealed what I thought at first was a bug in my code. Let me demonstrate:

At first glance, it appears that the light on each of these models is coming from a slightly different location. However, the same lighting direction is passed to all models. I thought perhaps the way I was transforming the world matrix was somehow affecting my lighting direction as well - I tried different things, pored through the code, and generally fumed ineffectually at the problem for several hours before finally writing to my instructor. Thankfully, he was able to quickly resolve my problem, if in a rather unexpected way.

It turns out the bug was not in the code but in my brain's perception of the scene. Because we have so little information to work with in this scene, and we're trying to interpret a 2D image as a 3D image, our brains actually come to the wrong conclusion. If there were more varied objects in the scene providing perspective, or if we were able to move around the scene, we'd reallize the truth - we aren't seeing all of the spheres from the same angle. The light IS hitting them all from the exact same direction, but our camera is not SEEING them all from the same direction.

The give-away is the texture. If you look closely you'll see the light is hitting the textures all in the exact same way on each sphere. The textures appear rotated differently on each sphere from our perspective, too, but they are all facing the same way, it's simply that we are seeing each from a slightly different angle. In fact, the only part of the light that is actually changing due to where we are in respect to the sphere is the specular highlight, because it's position depends on the camera location in addition to the lighting direction.

My mind was a bit boggled when I understood what my instructor was saying, and I admit I raged a bit at having wasted several hours on what was in fact not a bug. But it is pretty interesting to see first hand how our minds, when presented with a limited amount of information, can easily interpret things into a completely incorrect conclusion.

Creating a DirectX Scene - The Beginning

Remember back when I said I was working on a scene in DirectX? Yeah, that didn't stop being a thing. I've been spending most of my time with it so far simply getting used to the system, but I'm finally ready to start getting my hands dirty with the code.

This week, I've added a second model into the scene and learned to move, rotate, and scale the models. This will be essential if I want to have a believable space scene later on. I also unintentionally caused one sphere to orbit another due to a mis-ordering of transformations on my second model. I haven't decided if I want to try to use this method for orbiting planets in my scene or if I will use a less "cheaty" way of doing orbits.

My next goal is to clean up my code and remove hard-coded elements. I will create a uniform method for rendering a model, create an to hold my models rather than having a variable for each one, and work on how to render them using this array or a more object-oriented solution. After that, I'll be working on camera movement via keyboard input. And from there I should be in a good situation to start adding the more complex elements of the scene.

I'll be documenting my problems and discoveries along the way here on the blog, as I'll need all of that for the report due along with the program for my module.