Kosmonaut's Isometric Adventures

Hi guys,

I’m back. Maybe just for a short while maybe for longer.

I was sort of looking into making cool tooling for semi 2d isometric games.

Here is what i have so far:


(The GIF is there you just have to click on it…)

Because I know how important it is to work with pixel perfect assets when doing art like this the ground texture in this case is rendered in a way that every pixel of its texture is a pixel on screen, but the actual geometry is 3d and tilted away from the camera.

For quick sketching we can simply draw on the texture with in-engine tools and save them again to .png.

This sketching aspect is what’s most important to me - it should just work.

Obviously the textures can be refined in better tools afterwards.

4 Likes

Hey @kosmonautgames, this looks interesting.

I’m always curious what you come up with, because you already made some cool things in the past.

Nice to have you back! :fist:

I will also try to be more active again (and I also have something to show soon).

Seeing people like you coming back always motivates me to do the same :smiley:

Now some dynamically drawable sprites are available - they each write to a shared texture atlas!
They draw to the depth buffer, no sorting needed.

Here is what’s happening if you turn the camera - which it’s not supposed to do, since this is an iso game framework.

1 Like

Hello good to see you back kosmo.

Okay so for the first time in … ever I think i do not want to reinvent the wheel. I need some 2D collisions for polygons and I think I’ll check some solutions that already exist.

  1. Nez.
    Checked out the https://github.com/prime31/Nez-Samples samples again… very very impressive.
    I don’t think I want to build, since the whole workflow seems different than what i imagine using, but a lot of things to cherry pick. Collisions are solved beautifully.

I will continue checking other sources first like mg.extended and some google search

Update:

  1. Monogame.Extended
    i cannot get it to build on my machine. A shame. It targets.net core 2.0 and i don’t have the right SDK for that. Not looking to get that one, 2gb for the SDK is too much of a hassle for a simple test.
    I think it does not provide the collisions i need anyways, honestly just wanted to try it.

  2. Looked through some source samples, found this: https://www.codeproject.com/Articles/15573/2D-Polygon-Collision-Detection
    And this
    2d rotating polygon collision example using planes.

  3. Should check out Aether.Physics2D - Release v 1.0

Ya i probably didn’t write that little example intuitively i have always been a poor writer and the gif i had up is deleted by photobucket which really illustrated the idea. It’s pretty simple though hard to explain…

Ill try to state it succinctly and directly. For narrow phase polygon surface collision detection.
.

If you have two points A and B (in 2d this is a line and it can be considered equivalent to a plane in 3d).

B-A is a direction vector with A as a origin.

The direction vector and point A together can be considered to be a Ray.

When the direction vector is first normalized and then a perpendicular normal is found to it.
That normal is then said to be a Surface Normal as it is perpendicular to the plane, (which as previously stated in 2d is the line).
So in 2d it is a Surface Normal that is perpendicular to the polygon line AB.

A surface normal has one of two possible orientations to a plane which in 2D is the line.
In or Out.
This correlates directly to winding clockwise or counter clockwise.
Which in 2D is directly determined by selecting … B-A or A-B for the initial direction vector.
This in 2D is simplified to being a Left cross or Right cross product (in relation to the direction of the vector formed from a-b or b-a).
All three of these descriptions are synonymous.

Once this surface normal is known then any vertice of a opposing polygon, to be consider for collision with the surface of the initial polygon. Can be compared to find the directionallity between the two normals in scalar form. I.E. to get a In or Out result in the form of a floating point value.

Some secondary polygons point (denoted as) C, to the line A B of the first polygon.
Can be made into a direction vector by C - A
This is the same point A we used as the subtractor earlier for B - A.
The result is normalized.

These two normals that we have now found, the Surface Normal and the new Direction Vector
These two can be doted against each other to determine what side of the line a point is on.
This gives a result that has one of three possible signs that have a implicit meaning for collision.
A result of
0 is ON the line. (perpendicular normal pair)
-1 INside the line. (opposing normal pair)
+1 OUTside the line. (parallel normal pair)
Knowing if a vertice of a polygon is inside or outside of a line is rather meaningless in most cases however knowing if a opposing polygons vertice is inside of 3 lines of a triangle is knowing if a collision has occurred and then some.

So this process must be repeated for all 3 lines of a triangle or all the lines of a Convex polygon.
Concave polygons must be subdivided into 2 or more distinct groups of checks that are analogous to, a Concave equivalent of the original convex polygon.

The primary thing you test for is failure such that success is extensively not failing the tests.

Tthe dot and cross product can be combined in 2D. The cross and dot for B-A is shown below.

public static bool HasPointCrossedLine2d(Vector2 start, Vector2 end, Vector2 collisionPoint)
{
    Vector2 B = (end - start);  
    Vector2 C = (collisionPoint - start);

    // Cross right and dot 
    float sign = C.X * -B.Y + C.Y * B.X;

    // We only need the signed result.
    if (sign > 0.0f)
        return true;
    else
        return false;
}

So in summation.

For a 2d triangle with points C B A you can then see that B-A forms a line.
All polygons are composed of vertices that form lines.
Two triangles can be checked for intersections to vertices extremely cheap for two triangles with 100% accuracy in 6 checks.
via … float sign = A.X * -B.Y + A.Y * B.X;
The more complex the polygon geometry the more checks are required however other strategys can be employed to find a faster fail.
This technique is invariant under rotation.

A surface normal can be generated just like a lighting normal in a 3d calculation and use for collision and culling.

In fact that is exactly what this is in 2d and exactly what the gpu does in 3d (except with the 3d vector calculation) to determine backface or front face removal when the render state for culling is set.
This is just the 2d equivalent which is both simpler faster and gleems just as much information as 3d.

You can find reflection refraction and perform all familiar light normal operations in this context for collisions.
To say you can have a bullet or vertex hit your polygons surface and calculate the angle which it will be reflected off similarly to the way you find the angle for reflection of light on the surface of a triangle in 3d ect.

This is a very very old technique now and has been around since the 70’s and even in games in the 80’s.
Both complex ideologically and simple mathematically it is a fundamental concept for gpu’s and accurate surface collision detection in the narrow phase.

// standalone game1 test.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;

namespace NarrowPhasePolygonCollision
{
    public class Game1 : Game
    {
        public static GraphicsDeviceManager graphics;
        public static SpriteBatch spriteBatch;
        public static Texture2D dotTexture;

        public float autoRotZ = 0;

        Matrix polyWorld = Matrix.Identity;
        Matrix polyWorld2 = Matrix.Identity;

        public Vector2[] polygonPoints = new Vector2[]
        {
             new Vector2( 120,33),
             new Vector2( 120,76),
             new Vector2( 48,119),
             new Vector2( 17,106),
             new Vector2( 12,101),
             new Vector2( 48,8),
             new Vector2( 77,8),
             new Vector2( 108,25)
        };

        public Vector2[] polygonPoints2 = new Vector2[]
        {
             new Vector2( 122,44),
             new Vector2( 122,81),
             new Vector2( 73,117),
             new Vector2( 67,117),
             new Vector2( 11,82),
             new Vector2( 11,41),
             new Vector2( 65,4),
             new Vector2( 119,41)
        };

        //public Vector2[] polygonPoints3 = new Vector2[]
        //{
        //     new Vector2( 0,0),
        //     new Vector2( 100, 00),
        //     new Vector2( 100,100),
        //     new Vector2(  00, 100)
        //};


        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            Content.RootDirectory = "Content";
            graphics.GraphicsProfile = GraphicsProfile.HiDef;
            IsMouseVisible = true;
            Window.AllowUserResizing = true;
            graphics.PreferredBackBufferWidth = 800;
            graphics.PreferredBackBufferHeight = 600;
        }

        protected override void Initialize()
        {
            base.Initialize();
        }

        protected override void LoadContent()
        {
            spriteBatch = new SpriteBatch(GraphicsDevice);
            dotTexture = TextureDotCreate(GraphicsDevice);
            polyWorld.Translation = new Vector3(100, 100, 0);
            polyWorld2.Translation = new Vector3(100, 300, 0);
            Window.ClientSizeChanged += OnResize;
        }
        public void OnResize(Object sender, EventArgs e)
        {
        }
        protected override void UnloadContent()
        {
            dotTexture.Dispose();
        }

        protected override void Update(GameTime gameTime)
        {
            if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed || Keyboard.GetState().IsKeyDown(Keys.Escape))
                Exit();
            if (Mouse.GetState().LeftButton == ButtonState.Pressed)
                autoRotZ += gameTime.ElapsedGameTime.TotalSeconds.ToFloat() * 1f;
            if (autoRotZ >= 6.28f)
                autoRotZ = 0;

            var p = Mouse.GetState().Position;
            polyWorld.Translation = new Vector3(p.X, p.Y, 0);

            polyWorld2 = Matrix.CreateRotationZ(autoRotZ);
            polyWorld2.Translation = new Vector3(200, 200, 0);

            base.Update(gameTime);
        }

        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.CornflowerBlue);
            int w = GraphicsDevice.Viewport.Width;
            int h = GraphicsDevice.Viewport.Height;

            spriteBatch.Begin();

            TestCollisionAndDrawPolygonLineResultsIndividually(polygonPoints, polyWorld, polygonPoints2, polyWorld2);

            spriteBatch.End();

            base.Draw(gameTime);
        }

        /// <summary>
        /// 2d narrow phase point to plane collision.
        /// </summary>
        public static bool HasPointCrossedLine2d(Vector2 start, Vector2 end, Vector2 collisionPoint)
        {
            Vector2 n = (end - start);
            Vector2 n2 = (collisionPoint - start);
            if (n2.X * -n.Y + n2.Y * n.X > 0.0f) // Cross right and dot. We only need the signed result.
                return true;
            else
                return false;
        }

        /// <summary>
        /// Checks if a 2d convex polygon with a arbitrary number of vertices has collided with another by vertex comparison.
        /// </summary>
        public bool TestPolygonSurfaceCollision(Vector2[] polygonPointsA, Matrix worldA, Vector2[] polygonPointsB, Matrix worldB)
        {
            // test polygon 1 against polygon 2.
            for (int j = 0; j < polygonPointsB.Length; j++)
            {
                int checks = 0;
                for (int i = 0; i < polygonPointsA.Length; i++)
                {
                    int i2 = i + 1;
                    if (i2 == polygonPointsA.Length)
                        i2 = 0;
                    if (HasPointCrossedLine2d(Vector2.Transform(polygonPointsA[i], worldA), Vector2.Transform(polygonPointsA[i2], worldA), Vector2.Transform(polygonPointsB[j], worldB)))
                        checks++;
                    if (checks >= polygonPointsA.Length )
                        return true;
                }
            }
            // test polygon 2 against polygon1.
            for (int j = 0; j < polygonPointsA.Length; j++)
            {
                int checks = 0;
                for (int i = 0; i < polygonPointsB.Length; i++)
                {
                    int i2 = i + 1;
                    if (i2 == polygonPointsB.Length)
                        i2 = 0;
                    if (HasPointCrossedLine2d(Vector2.Transform(polygonPointsB[i], worldB), Vector2.Transform(polygonPointsB[i2], worldB), Vector2.Transform(polygonPointsA[j], worldA)))
                        checks++;
                    if (checks >= polygonPointsB.Length )
                        return true;
                }
            }
            return false;
        }

        /// <summary>
        /// This is all wastefully to visualize what is occuring piece wise per line.
        /// </summary>
        public void TestCollisionAndDrawPolygonLineResultsIndividually(Vector2[] polygonVectorsA, Matrix worldA, Vector2[] polygonVectorsB, Matrix worldB)
        {
            // For illustration purposes well redraw this all red if a collision has occured.
            // This time however we must check each point proper against all the collision surfaces of a convex polygon to make sure it is contained.
            //
            if (TestPolygonSurfaceCollision(polygonVectorsA, polyWorld, polygonPoints2, polyWorld2))
            {
                // draw polygons lines
                for (int i = 0; i < polygonVectorsA.Length; i++)
                {
                    int i2 = i + 1;
                    if (i2 == polygonVectorsA.Length)
                        i2 = 0;
                    var A = Vector2.Transform(polygonVectorsA[i], polyWorld);
                    var B = Vector2.Transform(polygonVectorsA[i2], polyWorld);
                    DrawBasicLine(A, B, 1, Color.Red, 0);
                }

                for (int i = 0; i < polygonPoints2.Length; i++)
                {
                    int i2 = i + 1;
                    if (i2 == polygonPoints2.Length)
                        i2 = 0;
                    var A = Vector2.Transform(polygonPoints2[i], polyWorld2);
                    var B = Vector2.Transform(polygonPoints2[i2], polyWorld2);
                    DrawBasicLine(A, B, 1, Color.Red, 0);
                }
            }
            else // is not colliding
            {
                // This will display if any opposing polygons points are inside each line this does not nessecariily mean there is a collision.
                // If so draw a yellow line 
                // else draw a green line.
                for (int i = 0; i < polygonVectorsA.Length; i++)
                {
                    int i2 = i + 1;
                    if (i2 == polygonVectorsA.Length)
                        i2 = 0;

                    var A = Vector2.Transform(polygonVectorsA[i], worldA);
                    var B = Vector2.Transform(polygonVectorsA[i2], worldA);

                    int checks = 0;
                    for (int j = 0; j < polygonVectorsB.Length; j++)
                    {
                        var C = Vector2.Transform(polygonVectorsB[j], worldB);

                        if (HasPointCrossedLine2d(A, B, C))
                            checks++;
                    }
                    if (checks > 0)
                        DrawBasicLine(A, B, 1, Color.Yellow, 0);
                    else
                        DrawBasicLine(A, B, 1, Color.Green, 0);
                }

                for (int i = 0; i < polygonVectorsB.Length; i++)
                {
                    int i2 = i + 1;
                    if (i2 == polygonVectorsB.Length)
                        i2 = 0;

                    var A = Vector2.Transform(polygonVectorsB[i], worldB);
                    var B = Vector2.Transform(polygonVectorsB[i2], worldB);

                    int checks = 0;
                    for (int j = 0; j < polygonVectorsA.Length; j++)
                    {
                        var C = Vector2.Transform(polygonVectorsA[j], worldA);

                        if (HasPointCrossedLine2d(A, B, C))
                            checks++;
                    }
                    if (checks > 0)
                        DrawBasicLine(A, B, 1, Color.Yellow, 0);
                    else
                        DrawBasicLine(A, B, 1, Color.Green, 0);
                }

            }
        }

        public static void DrawBasicLine(Vector2 s, Vector2 e, int thickness, Color linecolor, float rot)
        {
            Rectangle screendrawrect = new Rectangle((int)s.X, (int)s.Y, thickness, (int)Vector2.Distance(s, e));
            spriteBatch.Draw(dotTexture, screendrawrect, new Rectangle(0, 0, 1, 1), linecolor, ((float)Math.Atan2(e.X - s.X, e.Y - s.Y) * -1f) + rot, Vector2.Zero, SpriteEffects.None, 0);
        }
        public static Texture2D TextureDotCreate(GraphicsDevice device)
        {
            Color[] data = new Color[1];
            data[0] = new Color(255, 255, 255, 255);
            Texture2D tex = new Texture2D(device, 1, 1);
            tex.SetData<Color>(data);
            return tex;
        }
    }
}

In 3d it would look like so…
Though i didn’t set up a test for this probably bugged since i typed it straight out.

        /// <summary>
        /// 3d narrow phase point to plane collision.
        /// </summary>
        public static bool HasPointCrossedPlane(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 collisionPoint)
        {
            Vector3 n = Vector3.Cross(p1 - p0, p2 - p0);
            Vector3 n2 = (collisionPoint - p0);
            if (Vector3.Dot(n,n2) > 0.0f) // Cross right and dot. We only need the signed result.
                return true;
            else
                return false;
        }

        /// <summary>
        /// Checks if a 3d convex polygon with a arbitrary number of vertices has collided with another by vertex comparison.
        /// </summary>
        public bool TestConvexPolyhedronSurfaceCollision(VertexPositionColor[] polygonPointsA, int[] indicesA, Matrix worldA, VertexPositionColor[] polygonPointsB, int[] indicesB, Matrix worldB)
        {
            // test polygon 1 against polygon 2.
            for (int j = 0; j < polygonPointsB.Length; j++)
            {
                int checks = 0;
                for (int i = 0; i < indicesA.Length/3; i+=3)
                {
                    int i1 = i + 1;
                    int i2 = i + 2;
                    var p0 = polygonPointsA[i].Position;
                    var p1 = polygonPointsA[i1].Position;
                    var p2 = polygonPointsA[i2].Position;
                    if (HasPointCrossedPlane(Vector3.Transform(p0, worldA), Vector3.Transform(p1, worldA), Vector3.Transform(p2, worldA), Vector3.Transform(polygonPointsB[j].Position, worldB)) )
                        checks++;
                    if (checks >= indicesA.Length / 3)
                        return true;
                }
            }
            // test polygon 2 against polygon1.
            for (int j = 0; j < polygonPointsA.Length; j++)
            {
                int checks = 0;
                for (int i = 0; i < indicesB.Length / 3; i += 3)
                {
                    int i1 = i + 1;
                    int i2 = i + 2;
                    var p0 = polygonPointsB[i].Position;
                    var p1 = polygonPointsB[i1].Position;
                    var p2 = polygonPointsB[i2].Position;
                    if (HasPointCrossedPlane(Vector3.Transform(p0, worldB), Vector3.Transform(p1, worldB), Vector3.Transform(p2, worldB), Vector3.Transform(polygonPointsA[j].Position, worldA)))
                        checks++;
                    if (checks >= indicesB.Length / 3)
                        return true;
                }
            }
            return false;
        }
1 Like

Thank you very much!

I implemented your algorithm for some boxes first.

The real issue - it turns out - is not calculating if there is collision, but what to do with that information (how much the entity can actually move)

I played around and have some half-baked solution now:

The most naive approaches of the top of my head.
A is to pre-calculate the motion and if there will be a intersection and simply cancel or dissallow the motion to be applied.
For some single player situations this is fine it even works well. When the frame rate is high and small increments are made. Im other cases this maybe lacking.

B if there is collision to push a object away the problem with that is determining the order and correct situations were a push will actually create a set of improper motions. Such as pushing a entity into or thru other entitys.

Other ways

One is to pre-calculate the position and intersection and place the entity exactly at the limit of were it can move to, this is fine in some situations as well.

Yet another solution is to pre-calculate motion in one pass calculate intersections in time i.e. the fraction between frames the intersection occurred current to future and then perform collision physics at that moment to correct for the collision. This is pretty good normally unless there could be multiple simultaneous collisions at the same point at the same time.

Also don’t forget as well that this is just for narrow phase collision broad phase is still used with this typically such as a spacial grid or quad tree in 3d a oct tree or bsp ect.

prime31 has a port of box2d here if you want to see how he is handling physics i haven’t tried it but i have seen a few examples which are impressive.