Blarghlhargbl.

Uhm.
It's been some time.
So this is probably going to be a big update.
Haven't written it yet so I don't know.
Brb, writing the full blog post...



Yeah, it's a big one.
ITB: Talk about 2D platform AI (Artificial Intelligence), polygons, collision detection and GUI elements.
Alright, so.
One of the main topics I've worked on is enemy AI.
AI is always a huge problem, because it's a huge topic, very complex and needs a lot of consideration and work to get right.
I'm not going to use complex AI things, because it would consume too much time and wouldn't have too much impact.

The main AI aspect I have to solve is that the enemy needs to find a way to the player.
Usually, for things like this, path finding algorithms are used like A*.
However, those algorithms don't work well in a 2D platforming environment, because they can't find a valid way through...
let's say this:

The pink way is what A* or a similar path finding algorithm would see.
It simply looks for the shortest way.
This would be OK for a top down environment, or for flying enemies.
However, in a 2D platforming environment, this is unsuitable.
The green way is what would be correct.
Now, how do we approach a problem like this?

Take a look at this figure.
The only way to solve this is by trial and error approach.
The AI first checks all possible actions.
In our first case, this would be to go LEFT, DOWN RIGHT or UP RIGHT.
Each of the cases give a new distance to the goal.
The first logical thing to do is to choose the way that brings us closer to the goal.
After the AI made it's move, it reconsiders it's possibilities and repeats the same process every time the possibilities change.
However, just choosing the one that brings you closest isn't always the right way.
Consider this:

As you can clearly see, the first choice, C, wouldn't get us anywhere.
So we're forced to introduce randomness.
Intentional errors to, as contradictory as it sounds, increase the chance of doing the right thing.
But still, even with this, it's not very likely that the AI will find the right way.
It requires a lot of fine tuning and a huge lot of extra things to do, like secondary detectors, or trying to pre-calculate the outcome of a choice and so on.
I'm using a very simple approach here, but I'll probably improve it a bit still.

Have a screenshot:



Now, the next thing I'm going to talk about is polygons and collision detection.
I suppose you know what polygons are, so we'll get right to the collision detection aspect.

The principle behind collision detection with polygons is simple.
Take a look at this figure:

Basically what you do is follows:
Cast a ray from the point you want to check for collision out into a random direction.
Check the ray for intersections with every line segment of the polygon.
If there's an even number of intersections, the point lies outside of the polygon, otherwise inside.
This is a pretty neat and easy to understand principle.
And it always works.

The \"problem\" is more the intersection between ray and line itself.
To determine the exact collision point between line segment and ray, you expand both to a full, infinite line.
You then check the intersection point of the two, which will give you two values.
t being the position on the ray and u being the position on the line.
If t is negative, it would lie behind the ray point and can thus be automatically rejected.
If u is negative or bigger than one, the point lies outside the line segment and can be rejected too.
To determine the closest intersection point, you simply always save the t value and as you go through the segments, check if t is smaller.
The smallest t is the closest intersection point.

With this method, you can precisely determine the collision point between any possible 2D shape and a point.
Here, have a screenshot:


The problem I haven't solved yet is the texturing of the polygon.
This is mainly due to the problem that I can't draw polygons the conventional way.
OpenGL only supports drawing of convex polygons out of the box.
(Convex polygons are polygons that have nothing that bulges inwards)
To draw concave polygons correctly, you need to use Tesselation.
Tesselation basically tears apart the polygon and puts it together as fragments of concave polygons.
This however, makes texturing a bit problematic and I haven't found an explanation or way on how to do it yet.

I'll figure it out eventually.
Somehow.

I've also been working on the GUI elements some more.
So far I've implemented Buttons, Labels, Text Fields, Text Areas, Images, Lists, Scrollable Lists, Radio Buttons, Toggle Buttons and Panels.
It's quite annoying and quite some work to re-make all the GUI elements yourself.
I'm pretty sure there are GUI libraries for OpenGL/Java out there somewhere, but that's not what \"making your engine from scratch\" is.

There's nothing really fancy to show about the GUI yet, I have to integrate it into the game state loading system first.
I think I'll be able to show some sort of tech demo soon enough.
I'll also see that I can get this blog back up to a regular schedule.
Holding things back just makes them even worse to work back up on later.

And with that, I think I'm done for now.

-->Nick over and out!