Point'n click + Pathfinding (EasyStar)

[iiceman]

Well, if you click and things are moving something might move into your path after clicking... so just checking when clicking doesn't seem enough. But maybe you can slip thing sup. First scan the static terrain, build a matrix and keep that. And for the moving objects just keep track of them as they move and update your matrix according to their movements.

[Uniform]

9 hours ago, iiceman said:

Well, if you click and things are moving something might move into your path after clicking... so just checking when clicking doesn't seem enough. But maybe you can slip thing sup. First scan the static terrain, build a matrix and keep that. And for the moving objects just keep track of them as they move and update your matrix according to their movements.

Yep well If I knew a way to track the movements on the matrix it would be nice.

Unfortunately for now this is the only way I can do that. Passing an object through all the terrain and mapping the collisions inside a matrix..

However you are right and that objects might come into my path so I would probably need to scan the terrain every frame, or every 2 frames. I don't think that it will be that big of an issue. And if it is I can just create 4-5 abstract counters that will map the terrain into the matrix in an asynchronous way. 

 

So if someone knows how to do it it would be nice (What is the most effective way?). Manipulating the matrix directly based on every object's movements will be a lot of work on the cpu I think. Especially when the result of terrain mapping can be used for a lot of objects in the same time.

So I will probably implement a constant terrain mapping.

 

Would be great to hear from people familiar with pathfinding!

[iiceman]

I thought about something like that: http://www.babylonjs-playground.com/#Z3UOX#15

If you have a normal grid you can just round the values and calculate the position of an object on your grid. But still, I have no idea if that's a good solution or not

[adam]

@iiceman that is how I would do it. 

[Uniform]

4 hours ago, iiceman said:

I tohught about something like that: http://www.babylonjs-playground.com/#Z3UOX#15

If you have a normal gid you can just round the values and calculate the position of an object on your grid. But still, I have no idea if that's a good solution or not

If I am not mistaken this simply creates another mesh at the pointer's position. However it doesn't really change from what I have already. I mean imagine if you have 5 enemies and a player. That means that the game will need to constantly track their movements and map not simply a point in the matrix but 2d plane the base of the box to the matrix and also update the matrix when the mesh is moving.  

I think that if you have very few meshes that move your algo is more effective but if you have more mine is more effective because the Big O is the same and not depending on the amount of meshes, I run though the matrix anyway. And with 10 abstract objects instead of 1 it will be quicker I think. (or 30 objects that which will basically map a line each).

The issue I see with your algo is that you will have to somehow transport your point in space to a 2d plane in the matrix. However it can simply be set with a simple rounding and fulfill coordinates in a certain range from the center of the mesh algo.

 

Anyway thanks. I will try to deal with my stuff because It is more logical for me, If I have performance issues I will try your way of dynamically morph the matrix (which means that you also need to put 0 when the mesh exits a said position). I understrand that for a game like DOTA, with a big terrain that's probably the way to do it but I have a small terrain, more like an arena.

 

Anyway thanks a lot,

Uniform

[iiceman]

Sure, no problem. Good luck and let us know how it goes. Would be interesting to run some tests and see what method is better performance wise. I am still rooting for my approach since I believe you actually don't need an extra mesh, just the coordinates. If I have some free time and mood I might give it a try. What matrix size should I use and how many moving objects are to be expected?

[Uniform]

1 hour ago, iiceman said:

Sure, no problem. Good luck and let us know how it goes. Would be interesting to run some tests and see what method is better performance wise. I am still rooting for my approach since I believe you actually don't need an extra mesh, just the coordinates. If I have some free time and mood I might give it a try. What matrix size should I use and how many moving objects are to be expected?

Basically a player and 5 enemies. 

I am using Abstract mesh class instead of mesh class for the mapping counter. I know it's not rendered but I don't know if there is a big difference in performance.

The ground is 15 by 15. And the pointer abstract mesh that maps the terrain to matrix depending of the objects on the ground uses an incrementation variable of 0.5. That means it moves 0,5 on the x axis, checks if collision or not and moves further. When reached the end of the x axis it increments the z value by 0.5 and reinitializes the x axis value and continues to move and check the collisions.

 

A smaller incrementation variable value will lead to a bigger matrix, Obviously to avoid a biiiig but precise matrix it's better to add a bounding box bigger than the mesh itself to the pointer if you use a mesh to map the terrain or to any movable object.

 

So ground 15x15, matrix 30x30 because calculated with incrementations of 0.5.

Moving object: player + 5 enemies (static to begin with).

 

Somethimes the player goes through the sides of other object's boudning boxes. I though I will fix this by adding a second mesh that acts like a bounding box and more effectively add some scale to the pointer that maps the terrain to matrix but apparently it doesn't work very well so.

The workaround is probably a bigger matrix for more precision or a custom algo. However it's not big of a deal for the moment because my meshes will be characters and not boxes.

 

Sorry for the typos, got my first blank Das Keyboard today 

[Uniform]

@iiceman

 

A litte update.  I have done some profiling and it appears that running the mapping loop everyframe gives:

- 151ms in total  with a 15x15 terrain and 0.5 increments. (no lag signs)

- 670ms in total with a 30x30 terrain and 0.5 increments (no lag signs)

- 850ms in total with 15x15 terrain and 0.25 increments (no lag signs)

- 2k ms in total with a 30x30  terrain and 0.25 increments (some lags when a lot of mouse clicks)

 

Later I will try with "multithreading" increments. If I can't get something down to 151ms with 30x30 terrain and 0.25 increments I am gonna write something close to what you advised.

[Uniform]

Update:

Implemented the @iiceman way. Great performance, less than 40 ms lag with a 30x30 terrain and precision x4 (0.25 incrementations). 

Hacked a bit the Mesh class to store coordinates I will need to wipe out from the matrix as soon as the Mesh has moved.

 

The link is here: http://linguist-rodney-20561.bitballoon.com/ (check console)

 

Just wanted to ask if there is an easy method to detect a mesh's corners because I am using my code for the moment:

function generateFootprint(object){
    var width = object.scaling.x;
    var depth = object.scaling.z;
    var height = 0.1;
    var leftUp = new BABYLON.Vector3(
        object.position.x-width/2,
        height,
        object.position.z+depth/2
    );
    var rightUp = new BABYLON.Vector3(
        object.position.x + width/2,
        height,
        object.position.z + depth/2
    );
    var botLeft = new BABYLON.Vector3(
        object.position.x - width/2,
        height,
        object.position.z - depth/2
    );
    var botRight = new BABYLON.Vector3(
        object.position.x + width/2,
        height,
        object.position.z - depth/2
    );

    object.corners = [leftUp, rightUp, botLeft, botRight];
    //console.log(object.corners);
}

 

[iiceman]

Sweet! I started playing around yesterday a bit but didn't have enough time to finish it. Glad to hear that it seems to work for you! Can't wait for the first playable version

About the corner positions: you can check if AbstractMesh::getBoundingInfo() helps you - https://doc.babylonjs.com/classes/2.4/AbstractMesh#getboundinginfo-rarr-boundinginfo-classes-2-4-boundinginfo- - it contains quite some information about the different corners.