Need help to find best pathfinding solution for my next project (tower defense game)

mawa · August 12, 2024, 9:22am

Dears,

I need your insight on an early design thinking concept for my next project.
After years thinking of it, I thought now would be the time to finally start with this.

Goal is to create a TD (tower defense) game using our favorite tool/toy.

My first challenge is finding the right/best approach and logic for pathfinding.

It’s gonna be a (half-)traditional TD. The traditional part is that it will be based on a grid/cells. On the grid, You can build towers in any free cell (or destroy them) except of course, in the cells from the static map(s) that are obviously (static) obstacles.

Obviously, the path for enemies will have to update dynamically (and seamlessly) when you place remove new dynamic obstacles (towers).

But then, of course (or I wouldn’t ask) there’s more to it:

Here are some of the identified requirements:

There will be more than just one instance of pathfinding. The first one is the one for the enemy (and enemy waves). It should take the shortest path at all time, both from the static and dynamically added or removed obstacles. The second is to handle the player units on the map/cells. Some towers can spawn a crowd (2 or 3) melee units that can be placed on the enemy path within a certain range from the tower/barrack.
Obviously, when the enemy comes in range of an allied melee unit, the melee unit will attack the enemy. The correct behavior is that (while still attemting to move towards its goal/end point) the enemy will be cought in battle. If by any chance the enemy manages to clear the allied unit (that can be seen as an obstacle I believe), it needs to resume its path towards reaching the end point.
Both allied and enemy units of course, need to be able to collide with obstacles when either resuming their path (in the case of enemies) or when setting a new origin spawn point (for allied units).

So, I visited a fair a number of links and solutions and it looks like they really all have their pros and cons. Reason why I’m seeking your expertise. Any thoughts, advise, example, PG or tutorial would be welcomed and highly appreciated.

Some other aspects to consider:

despite the fact that it is based on a grid/cells and will most likely use a static view camera (isometric-like), the map will still be 3D (with some heights like bridges or small hillsides). Means the path will in fine be 3D. In fine, because to move on the grid/cells, the height coordinates might not be absolutely necessary (so I thought, correct?). May be using a 2D version and handling just the animations from the ground/height map/collision would be an option?
last but not least, although I’m just working on a pilot (and at a very early stage), the goal is indeed to have a number of maps. Means the solution (or mix of solutions) needs to be kinda easy to manage. I will likely want to actually create a map editor and will want to be able to test and visualize the different scenarios.

So, yes, given all the above… what should I do? use the provided with BJS? use external? 2D or 3D? use webworkers? what type of grid? use the 2D GUI texture or use coordinates?

Here are some of the references I found in my research:

From the crowd navmesh of BJS:

From external, suggested by @codingcrusader (seems interesting to me, but how to implement?)

https://qiao.github.io/PathFinding.js/visual/

Lots of doubts and questions at this very early stage. I’m also a total noob for this thingy. I need your help and invaluable knowledge to orientate me and guide me towards the first steps (or this game thingy will never see the daylight of the public Internet). In particular if you Guys have a minute, I’m thinking of @cedric, @Joe_Kerr and of course as always when it comes to complex things and a creative mind @CodingCrusader

EDIT: Forgot to mention (if it’s not yet already clear from the text above ): It’s really just if you have time and feel like it There’s no urgency. I’m gonna continue my research and also have tons of other aspects to figure at this very early stage

Cedric · August 12, 2024, 12:14pm

If everything can be placed into a dynamic 2D grid, I’d use a simple A* implementation.
It’s easy to code and maintain. It’s fast to compute (depending on the grid size).
More complexity can arise if there is multiple possible floors per grid cell.
Navmesh is great for complex polygonal level (like FPS maps).

mawa · August 12, 2024, 12:21pm

Thanks a lot for taking the time to look at this.
As said, I’m a complete noob with this … so I just have to ask: When you say ‘A*implementation’ you are referring to the algorythm, right? Fair enough. That was also my thought. But then, which method would you recom to implement. Is there a resource available in BJS or should I use external? Any link/example you could share? Thanks again and have a great day

Cedric · August 12, 2024, 12:25pm

A* is not complex and I highly recommend you to implement your own version as it looks like being one of the core feature.
a quick search gave me this :

mawa · August 12, 2024, 12:33pm

Oh! Thanks a lot for the resource and recom. Honestly, since I’m totally new to this, I didn’t consider the custom version. However, you may be right (you probably are). A custom implementation in the end might be less of a bother than trying to force adapt an ‘out-of-the-box’, partly inappropriate solution. Food for thoughts … I will take some time to further investigate this while waiting for the others to reply and while continuing my search… By any means, it cannot harm me to learn a bit more about how this work.

CodingCrusader · August 12, 2024, 2:23pm

If you are looking for the sourcecode. Here we are: qiao/PathFinding.js: A comprehensive path-finding library for grid based games (github.com)

How to implement? It’s the same how to draw an owl:

Import the js library
Code the rest

:-p

mawa · August 12, 2024, 2:53pm

Haha. Feeling playful, are you? Fair enough, deserved I suppose. Probably I also didn’t make the right choice of words when I said ‘implement’. So, I do have the code and I know how to load a library I also did draw an owl once or a couple of times… but it never looked like the original

So, I guess the question was more about what’s in the rest of the post. Is it appropriate? Should I work with cells or coordinates and blabla? you know things like said in the intro: “design thinking”.

labris · August 13, 2024, 2:05am

I tested PathFinding.js with Dungeoneer and it works well

Teal cubes show the path from one given point in the grid to another.
If anybody is interested I can publish the repo.

mawa · August 13, 2024, 9:02am

Thanks for your reply. Don’t know how I forgot to ping you on this I highly appreciate you still took the time to look at this.

And… you are right. At the current, pathfinder.js is my second option. I’m currently half/half between the suggested by cedric custom version from a standard a-star or (if external) pathfinder.js seems like the best solution so far.

After a good night of sleep and a few degrees less on the thermometer (although it will go back up to 35° this afternoon ), things are a little bit clearer to me.

Thanks to the input received and also because I wrote it down (probably) I’m starting to build-up on a scenario (at least in my head ). Getting LOLed by @CodingCrusader is also always motivating So, I made a couple of decisions that now exclude a number of ‘variables’ or ‘alternates’ and makes it easier for me to extend on a logic.

Two things are now clear to me and become ‘fixed’ parameters of the game design:

I will definetely go with the A* algorythm. The management of the height on the map (which will be very low heights) will be made separately. Either through collision with the ground or just a fixed input (per cell)
It will definetely be tiles/cell based and the size of each tile/cell will be fixed. The default/standard camera view (scale) will also be fixed. If a map/grid is bigger than the camera view, will use panning. Having fixed size tiles will help with consistency when spawning towers and units (and visually, consistency in design throughout the maps of different size).
the center point of cell origin will become the waypoint for the pathfinding.

This morning I have started to implement and create a quick test PG using the astar with binary heap (improved version) of the link provided by cedric. I’m working on setting-up a quick graph/visualizer and at the same time, the base of a ‘map editor’. It’s gonna take a bit of time but it’s fairly slick (and fairly ez as cedric said). If I’m stuck with it and does not work as expected, I’m gonna give pathfinder.js a try.

'Will keep this thread open for now and will publish my process and results.
Meanwhile, thanks again for your input and have a great day

labris · August 14, 2024, 12:33am

Another option, especially for arbitrary graphs, is to use NGGraph library - GitHub - anvaka/ngraph.path: Path finding in a graph
It is extremely fast and supports weighted graphs, oriented graphs, blocked paths and has several A* finders.
Here is the PG implementation - https://playground.babylonjs.com/#13HA0R#31

Left mouse button = add Node;
Right mouse button = add Link;
Middle mouse button = find Path.

image695×583 31 KB

jelster · August 14, 2024, 4:29am

You can easily incorporate the A* path finding with your map and terrain by creating a N-color BMP. At runtime you read the bmp and project it onto your grid system pixel by pixel to (it’s easier if you use the same image size as your map size). The color of the pixel can be interpolated or stepped to map into a terrain cost table that then drives the a* search.

So like red = 2 cost, blue = 1, etc… the algorithm uses those weights when determining the open or closed sets of route tiles.

Happy to go into more detail, feel free to reach out. I built a similar TD game many years ago in C# and XNA Game Studio

Ed to add: I think you’ll reallllly want to try to run your pathfinder as a web worker or otherwise asynchronous process that won’t run on the UI thread, if possible. You can create an Observable that fires whenever the path finder has produced a new result, allowing a path calc to run across multiple frames.

mawa · August 14, 2024, 10:50am

Thanks for the note but I’m clearly not going to rewrite the algorythm (nor even mess with it). I’m just not qualified for that but, more importantly, I have no use for it in this usecase.

mawa · August 14, 2024, 11:03am

Thanks both. Much appreciated although I have to admit I fully understand only parts of it at the moment

Anyways, I figured I have no need for this level of ‘complexety’. Hopefully, will not find out at a later stage that I would actually need it For now, I’m looking at (and ‘test-building’) just a very simple ‘cell based’ (or per cell, if you prefer) map/grid logic. The only cost I have is the one of the shortest path. I’ve got no terrain modifiers (for sure I won’t have) and for whatever offsets I will have (for my melee units or enemy units entering melee combat) they won’t be from the path itself (so I thought , hopefully not missing anything). So, I believe I have no need of a pixel by pixel grid system. Thankfully, this project remains fairly simple in this aspect (there are a lot of other aspects I have no faen clue how I’m gonna deal with ). But even this simple case is actually challenging me. I’m a visual person, not a dev - so I definetely need to build a bit on it before eventually realizing that this won’t work… or hopefully, ‘incidentally’ I should say, will work and be appropriate

mawa · August 14, 2024, 11:13am

You wouldn’t happen to have a link to share?
I’d love to have a look at it to see how close it actually is to my project.

Yes, I suppose you are right there. I’m only just starting to evaluate/realize how many times it will have to be updated and instanciated… and already feels like a lot.

jelster · August 15, 2024, 1:02am

That may indeed be the case, however keep in mind that in order to figure out the shortest path, each grid cell will be assigned a “cost” by the algorithm - whether that cost is weighted by terrain types (e.g., grass, mud, water) or not. Units will need to periodically re-run pathfinding as the environment changes - think of the “tower” aspect – if players are allowed to place towers in arbitrary spots, you’ll need to have a way to know if the position selected would block all routes to the goal and therefore should not be allowed.

OTOH, if you have pre-determined paths that will always be the same, then you don’t even need pathfinding. You can pre-compute a set of coordinates to serve as “waypoints” for the unit to travel. I recall starting with the latter then iterating a lot until I eventually fell onto the former approach with dynamic pathfinding. All depends on your goals!

It was a project for Windows Phone 7 RIP - unfortunately I don’t have a working build of the application anymore, but I do have portions of the source code relevant to this topic, but the repository isn’t public IIRC and since GH is currently down I can’t verify that lol.

Happy to share more if there’s interest I can certainly dig that up from whatever dusty source code archive I stored it in

mawa · August 15, 2024, 10:24am

Thanks, yes. This is precisely what’s in my mind at the moment. I’m just not sure to understand how adding weight to the terrain will help in this aspect? This is all too much unclear to me at the moment (sorry, as I said, total noob with this )… Reason why, I chose to start by creating just a very simple mock-up (that’s also a learning/&training scenario for me). I hope from there I will be able to get a better image and understanding of how it will work (and all work together).

Yes, of course. That would have been the easiest But no, the core of the gameplay is definetely that you can dynamically build a ‘maze’ by placing towers. However, it remains ‘fairly simple’ in that the enemy also always takes the shortest path (disregarding additional costs such as terrain modifier or potential damage taken). They will always follow the shortest path, giving the player the opportunity to choose between building on a maze to make the path longer or make less towers with a more direct path. While of course each tower and upgrade has a cost (no need to mention). So, there’s a choice of strategy between making the path longer with less damage or keeping the path short will dealing more damage to the enemy (or a combination of both )

You’re so good to me I’ll keep your offer and will certainly return to you at some point Meanwhile, I think it’s fair for everyone (and good for me) that I would continue to struggle a little and set-up this first version case scenario PG. At least, we’ll have a base to work from (and I do need this training and visual representation for my low brain ).

…and all the above is precisely because of that. That’s just typically what I’m trying to avoid So, no matter if I have to flush everything from this ‘training scenario’ and start completely new. A couple weeks for this won’t do anything. Not as if someone would be waiting on it. But since there will clearly be a lot built on top of this logic and aspect of the game, I wanna make sure I take the option that’s both appropriate and which I can also keep under control/understand.

Thanks again and meanwhile, have a great day

EDIT: OOps, a second thought. Typically me, I start thinking only AFTER typing

For

May be I could use this additional ‘terrain weight/cost’ to early determine if you actually can build a tower or not (because it would block the path). Is that the logic you were thinking of? Say that when I generate a new path, I would at the same time record whether there’s just a single path left open… If so, at this very moment, I could record the ‘weight/cost’ as ‘critical’. Then when attempting to place a new tower on a tile that has ‘critical’ weight, requirements would be that at least one neighboring cell(s) left ‘free’. Is that kind of a logic or is it just plain bullshit?

Finally, as I sidenote, probably worth to mention that you can also ‘unbuild towers’ and some enemies have the ability to ‘destroy’ a tower. Which, in turns, means that in all these cases and including at the start of a new ‘wave’ of enemies, a new path will have to be generated. Plus the handling of the enemies that are already on the shortest path according to their current position/waypoint. Like I don’t want them to go back because there’s a ‘new’ shortest path from start to end. So,yes, I said ‘simple’… but clearly, things are never just completely ‘simple’ speaking of a game design

jelster · August 16, 2024, 3:06pm

Yes, that’s the idea in general. Because path finding is basically a middle-tier application service to your game components, it’ll appear in a number of places. Your A* search component that actually performs the path finding logic will be a lower-level service consumed by the PathManager, which also has a reference to the Level instance along with some tile/grid mapping functions. Apologies for the long code listing hidden below, it’s not the complete picture but hopefully it’s a good start!

Path Manager Component


public class PathManager
    {
        private LinkedList<MapNode> _path = new LinkedList<MapNode>();
        
        private TileDimensions _actorSize;
        private AStarSearch SearchComponent { get; set; }

        public Map LevelMap { get; private set;}
        public bool IsPathAvailable;
        public bool IgnoreTerrain;
        
        public PathManager(Game game, Map levelMap, TileDimensions worldTileSize, TileDimensions baseSize, bool ignoreTerrain)
        {
            _actorSize = baseSize;

            IgnoreTerrain = ignoreTerrain;
            SearchComponent = new AStarSearch(game) { Type = SearchType.EightWay, Configuration = SearchConfiguration.NotTimed };
            SearchComponent.Game.Components.Add(SearchComponent);
            SearchComponent.OnSearchFinished += SearchFinished;
            
            var map = new Map(levelMap.Nodes);  //make local copy so we can adapt to the actor's size
            UpdateMap(worldTileSize, _actorSize, ref map);
            LevelMap = map;
            
            SearchComponent.Map = LevelMap;
           
        }

        protected internal void UpdateObstacles(object sender, MapInvalidatedArgs args)
        {
            //TODO: test and check this math
            var scaleX = _actorSize.X/args.TileSize.X;
            var scaleY = _actorSize.Y/args.TileSize.Y;

            //NOTE: possible boxing here with foreach
            foreach (var node in args.ChangedNodes)
            {
                if (args.TileSize == _actorSize)
                {
                    LevelMap.Nodes[node.Position.X, node.Position.Y].Navigable = node.Navigable;
                }
                else
                {
                    var newPosX = (int)Math.Floor((double)node.Position.X / scaleX);
                    var newPosY = (int) Math.Floor((double) node.Position.Y/scaleY);
                    LevelMap.Nodes[newPosX, newPosY].Navigable = node.Navigable;
                }
            }
        }

        public void ChangeNodeNavigationStatus(Vector2 initialPosition, Vector2 worldPosition)
        {
            var node = GetCurrentMapNode(worldPosition);
            node.Navigable = !node.Navigable;
             
            if (_path.Any(x=> x == node && !x.Navigable) && !IgnoreTerrain)
            {
                LevelMap.StartNode = GetCurrentMapNode(initialPosition);
                IsPathAvailable = false;
                SearchComponent.Start();
            }
        }

// method bodies elided for brevity
        public Point WorldPositionToTilePosition(Vector2 worldPosition)
        public static Vector2 TilePositionToWorldPosition(Point tilePosition, TileDimensions tileSize)            
        public static Point WorldPositionToTilePosition(Vector2 worldPosition, TileDimensions tileSize)
        

        /// <summary>
        /// Returns the origin (in world coordinates) of the specified tile
        /// </summary>
        /// <param name="tilePosition"></param>
        /// <returns></returns>
        public Vector2 TilePositionToWorldPosition(Point tilePosition)
        {
            return TilePositionToWorldPosition(tilePosition, _actorSize);
        }

        public static Rectangle GetTileBounds(Vector2 worldPosition, TileDimensions tileSize)
        {
            return new Rectangle((int)worldPosition.X, (int)worldPosition.Y, tileSize.X, tileSize.Y);
        }
        public Rectangle GetTileBounds(Vector2 worldPosition)
        {
            return GetTileBounds(worldPosition, _actorSize);
        }
        public Rectangle GetTileBounds(Point tilePosition)
        {
            var tP = TilePositionToWorldPosition(tilePosition);
            return GetTileBounds(tP);
        }

        public void FindPath(Point origin, Point destination)
        {
            if (IgnoreTerrain)
            {
                _path.Clear();
                _path.AddLast(LevelMap.Nodes[destination.X, destination.Y]);
                IsPathAvailable = true;
                return;
            }

            LevelMap.StartNode = LevelMap.Nodes[origin.X, origin.Y];
            LevelMap.EndNode = LevelMap.Nodes[destination.X, destination.Y];

            SearchComponent.Start();
        }
        public void FindPath(Vector2 origin, Point destination)
        {
            var currentPos = GetCurrentMapNode(origin);
            FindPath(currentPos.Position, destination);
        }

        public void FindPath(Vector2 origin, Vector2 destination)
        {
            var destPos = GetCurrentMapNode(destination);
            FindPath(origin, destPos.Position);
        }

        public void UpdateMap(TileDimensions newSize)
        {
            var oldMap = LevelMap;
            UpdateMap(_actorSize, newSize, ref oldMap);
        }

        private void UpdateMap(TileDimensions oldSize, TileDimensions newSize, ref Map nodeMap)
        {
            if (newSize == oldSize)
                return;

            var scaleX = newSize.X / oldSize.X;
            var scaleY = newSize.Y / oldSize.Y;

            var oldTileCountX = nodeMap.Rows;
            var oldTileCountY = nodeMap.Columns;
            var newTileCountX = oldTileCountX / scaleX;
            var newTileCountY = oldTileCountY / scaleY;

            var newMap = new Map(newTileCountX, newTileCountY);
            MapNode newDestTile = null;
            MapNode newStartTile = null;

            foreach (var node in newMap.Nodes)
            {
                var oldNode = nodeMap.Nodes[node.Position.X*scaleX, node.Position.Y*scaleY];

                var n = nodeMap.GetNeighborhood(oldNode, SearchType.FourWay, SearchOrientation.Clockwise);
                n.Add(oldNode);
                var nav = n.Average(x => x.NodeCost);
                node.NodeCost = (int)nav;
                if (nav > 6)
                    node.Navigable = false;
                else
                    node.NodeCost = (int)MathHelper.Clamp(node.NodeCost - (scaleX + scaleY)/2, 0, 200); //easier for bigger creatures to traverse terrain

                if (oldNode.Navigable)
                {
                    //nodeMap.Nodes[newPosY, newPosX].Navigable = true;
                    if (nodeMap.EndNode != null && oldNode == nodeMap.EndNode)
                        newDestTile = node;

                    if (nodeMap.StartNode != null && oldNode == nodeMap.StartNode)
                        newStartTile = node;
                }
            }

            nodeMap = newMap;
            IsPathAvailable = IgnoreTerrain ? true : false; //TODO: determine whether path is still valid to short-cut
            
            if (newDestTile != null)
                nodeMap.EndNode = newDestTile;
            
            if (newStartTile != null)
                nodeMap.StartNode = newStartTile;
        }

        public bool IsPositionNavigable(Vector2 location)
        {
            var pos = WorldPositionToTilePosition(location);

            if (IgnoreTerrain)
                return LevelMap.Nodes[pos.X, pos.Y].NodeCost < 200;

            return LevelMap.Nodes[pos.X, pos.Y].Navigable;

        }
        public void GetPathWaypoints(ref Queue<Vector2> waypoints)
        {
            if (null == waypoints)
                return;

            waypoints.Clear();
            if (SearchComponent.State == SearchState.FinishedFound || IgnoreTerrain)
            {
                foreach (var node in _path)
                {
                    waypoints.Enqueue(TilePositionToWorldPosition(node.Position));
                }
            }
        }

        private MapNode GetCurrentMapNode(Vector2 pos)
        {
            var tilePos = WorldPositionToTilePosition(pos);
            return LevelMap.Nodes[tilePos.X, tilePos.Y];
        }

        private void SearchFinished(object sender, SearchFinishedEventArgs e)
        {
            if (!e.Found)
            {
                IsPathAvailable = false;
                return;
            }
            
            IsPathAvailable = true;
            _path = SearchComponent.Path;
        }


        public bool CanPlaceAtPosition(Vector2 position, Vector2 foodOrigin)
        {
            var start = WorldPositionToTilePosition(position);
            var destTile = WorldPositionToTilePosition(foodOrigin);

            if (!LevelMap.Nodes[start.X, start.Y].Navigable)
                return false;

            if (start == destTile)
                return true;

            SearchComponent.OnSearchFinished -= SearchFinished;
            var oldStart = LevelMap.StartNode;
            var oldEnd = LevelMap.EndNode;
            

            var placedNode = LevelMap.Nodes[start.X, start.Y];
            placedNode.Navigable = false;
             
            LevelMap.EndNode = LevelMap.Nodes[destTile.X, destTile.Y];
            var valid = false;
            
            //pick nodes from around the map and sample to see if there are still paths from them to the food
            var nodeList = new MapNode[]
                               {
                                   LevelMap.Nodes[0, 0], 
                                   LevelMap.Nodes[LevelMap.Rows - 1, 0], 
                                   LevelMap.Nodes[LevelMap.Rows-1, LevelMap.Columns - 1], 
                                   LevelMap.Nodes[0, LevelMap.Columns -1]
                               };
            
            foreach (var node in nodeList)
            {
                var mapNode = node;
                if (node == LevelMap.EndNode || !node.Navigable)
                    mapNode =
                        LevelMap.GetNeighborhood(node, SearchType.FourWay, SearchOrientation.Counterclockwise).First(
                            x => x.Navigable);

                LevelMap.StartNode = mapNode;
                SearchComponent.Start();
                SearchComponent.Update(new GameTime());
                if (SearchComponent.State != SearchState.FinishedFound) continue;

                valid = true;
                break;

            }

            SearchComponent.OnSearchFinished += SearchFinished;
            SearchComponent.Map = LevelMap;
            placedNode.Navigable = true;
            LevelMap.StartNode = oldStart;
            LevelMap.EndNode = oldEnd;
            return valid;
        }
    }

since I’m already at it might as well go further and show the relatively simple HeightMapGenerator that reads in a Bitmap (Texture2D) and maps colors to node (terrain) costs:

Height Map Generator


public class HeightMapGenerator
    {
        //TODO: make this into a content processor, read in list of heights/colors
        private readonly Dictionary<Color, int> HeightList = new Dictionary<Color, int>();
        public HeightMapGenerator()
        {
            HeightList.Add(new Color(127,51,0,255), 2);
            HeightList.Add(new Color(0, 127, 14, 255), 1);
            HeightList.Add(new Color(0, 0, 255, 255), 100);
            HeightList.Add(Color.Black, 200);
        }
        public HeightMapGenerator(Dictionary<Color, int> colorList)
        {
            HeightList = colorList;
        }

        public int[,] GetHeightMap(Texture2D texture)
        {
            var mapPixels = texture.To2DArray();
            var heightMap = new int[mapPixels.GetLength(0),mapPixels.GetLength(1)];
            
            for (int x = 0; x < mapPixels.GetLength(0); x++)
            {
                for (int y = 0; y < mapPixels.GetLength(1); y++)
                {
                    var color = mapPixels[x, y];
                    if (HeightList.ContainsKey(color))
                    {
                        heightMap[x, y] = HeightList[color];
                    }
                }
            }

            return heightMap;

        }
    }

Joe_Kerr · August 19, 2024, 9:54am

Sorry @mawa for the delayed response. Was on vacation :o

re 3D: the question is whether tiles overlap on the z-axis. If not, you can probably solve it with 2d only.

re requriements: Do player units always reuse the “enemy path”? Or can they be placed anywhere and need to find their own path to the enemy? If so, how many max independent player units will there be at one time? If the number is high, you might need to look into path fidning algos for real time stragety games.

Anyway, just a brief rundown where I ended up (turn based strategy game; few infrequent path finding queries). I pretty much adapted the Redblob algorithm. Their approach is nice because it reduces your work to implement a “checkNeighbour” function. There you can handle all game rules pertaining to tile/node’s “walkability” and/or “traversability”. In my case, I decide by lookup tables, i.e. tile flags (blocked?) and fences (sth blocking traveral from tile a to b). Note that this is all dynamic. Also note that “neighbours” can be in 3d space as well.

One thing to note is that performance is slightly worse than Babylon’s Recast. By that I mean if I wiggle the mouse like a maniac (generating pathing request on mousemove), I am getting noticably more frame drops in the Redblob algo compared to Recast.

You sure about that? This is going to delay your project for half a year. Have you seen @Dad72 existing map editor? Or Blender is actually not too bad for map creation (including scripting (=automation) API).

mawa · August 22, 2024, 10:42am

Thanks both @Joe_Kerr and @jelster for ‘anticipating’ my future challenges and trying to provide solutions for the ‘big picture’. Sure I will soon want to integrate this part in my building-up on my case scenario. In fact, I’m nearly there… but not quite there yet . As I said, total noob with this - and it’s only once I will have the visual and did things myself (at least a couple of times or a few times ), that my low brain will eventually trigger a ’ eureka!’

Knowing this, I started to build a PG from the ‘core logic’ I thought would be worth evaluating.
The idea/scenario is to make everything work around a cell based but also object based (or in other workds, mesh based) logic. Meaning the map/grid is generated and piloted from meshes/planes. Each cell/tile is a plane and its ‘state’ is set and handled through the ‘mesh.id’ and ‘mesh.name’ (and eventually material, if later needed as a third option/parameter).

This PG uses the ‘bgrins/javascript-astar’ (suggested by @Cedric) as the pathfinder algorythm.
For the ease of viewing, having everything at hand, I simply copied the script on top of the PG.
Astar by bgrins (original, unmodified): Lines #1 to 404.

Therfor, The PG itself starts on line #407
Currently in this PG, and despite the parts ‘hardcoded’ (or simulated), I do have this part of logic working. At first the map/grid is generated from a number of variables (for rows, columns and tile size). In the end I get a number of cells according to the ‘maplength’. Each cell/plane as an identifier in its ‘mesh.id’ which sets the state of the cell.

There are currently four identified ‘states’ for interacting with cells.

cell is open to the enemy - is not ‘buildable’. These cells highlighted yellow/greenish in the visual are the ‘start’ and ‘end’ spawning areas for the enemy. They are basically the cells that need to be left open for either ‘spawning’ (on start path) or (on end path) the part that is beyond the flag. No towers can be built on these cells and these are always left open for the enemy/pathfinding.
cell is ‘fixed obstacle’ - is neither ‘buildable’ nor ‘walkable’. Typically rocks, walls, trees… fixed obstacles from the map build, that are set only once on map creation.
cell is ‘free’ - can build and can walk. The cell can be interacted with to build a tower.
cell is ‘tower built’ - can upgrade or destroy and is non walkable. A tower is built on this tile, blocking the path.

Now, this is the part I currently have in this PG. I added some colored materials for visualization.

The other part that’s also implemented (and works) is changing the state of the cells through interaction and dynamically generate a new graph array AFTER change. When adding or removing a tower, the cell/mesh.id is changed to the new state and the state (1 for is walkable, 0 for is blocked) is pushed to the new graph array.

CHALLENGE #1 : JUNIOR LEVEL
And this is where I’m already stuck . Because of my lack of understanding of just basic js with the handling of arrays. For at least 3 hours, I have been trying to rebuild my new graph array to match the form of the input graph needed to invoke the astar pathfinder.

I know it must be just some very basic/stupid error of mine. I hope one of you could just quickly spot it, amend it and next…lol me and (optionally) explain where I was wrong (like speaking to a four year old).

The challenge is turning the ‘graph_array’ (first declared on line #555) and next updated/replaced through the 'change state function (‘cellState’ on line #606)… turn this ‘graph_array’ into an array with subarrays that can be used as a ‘new Graph’ (on line #744 - currently commented in this PG).

CHALLENGE #2 : INTERMEDIATE
Once this will finally be fixed, l also realized that the new path sort of doesn’t account the ‘start’ on the first row. For some reason, the new path (currently simulated in this PG - until challenge #1 is fixed) draws only from the second row. You can see this in the PG, by clicking on ‘generate path0’ (as opposed to the original/first) that’s the button to the right ‘generate path’. I don’t know why the start, even though being invoked as a ‘new start’ seems to be ignored somehow? Probably just another very basic stupid mistake of mine … or something else¿

CHALLENGE #3: ADVANCED
Once the above will prove workable (hopefully), then the real shit can start. Obviously, before even allowing to interact with a tile to build a new tower, I’m gonna need this predicate sort of mecanism. May be even will need to account neighbooring cells. Probably will have to

So here is where I thought this could be/should be managed through the ‘weight’ (or terrain cost). Just thinking of it ‘high-level’, I thought it would be smart/appropriate to do it already when generating a new path. All cells that would block the path would return with a weight value that can be used in the mesh.id to disable possible interaction with this cell (the cell becoming an ‘obstacle’ for tower building). Needless to say that I have no faen clue how to do this from the current script of astar chosen for this playground. Furthermore, I don’t know if - according to this scenario - this script can or should be used (or should be replaced through one of the others suggested in the replies above).

So, that’s where I stand at this moment - also still evaluating if this entire logic for a ‘game design’ is any good? or should be flushed altogether?

Your answers to any (or all ) of the above would indeed be highly appreciated. No rush though, as I said, nobody (not even me) is really waiting on this for an agenda.

EDIT: Forgot to mention that this PG is done in the outmost ‘explicit’ form. Making it of course much longer than needed (and with lots of testing and commented parts, sry). But it also makes it a lot easier to understand (at least for me) - and this is just what I needed at this stage

Joe_Kerr · August 22, 2024, 11:31am

You probably do not want to hear that. And it might just be me. But I think you PG code is quite extensive.

You probably will do this anyway later on. So would it be possible to put the code into a (temporary) github repo (including proper classes/files)? If you had that, then you could easily write a unit test against e.g. challenge #1. This failing unit test would be the equivalent of “make a playground so that we can help you”.

Ok, if not, then can you at least clean up the playground? All that dependency shit is noise. So is the UI code. So is the mesh/material setup. I would put all the noise way down. Ideally in functions so that it can be collapsed.

As for the “not-noise” (which is hard to discern!!!). Please put your code into functions and/or classes. For instance, I have seen a couple of code comments: e.g. “//BUILD MAP - Spawn cells on rows and columns” becomes e.g. function buildMap() : Cells[]

Maybe start with challenge #1. Put that into a playground. Can you maybe compress it down to a console.log that prints the current data and a comment that indicates the desired data?

Topic		Replies	Views
A.i enemies tf.js Questions	1	1238	April 22, 2019
3d pathfinding / flying ai Questions	4	2048	April 30, 2019
Examples of Tunneling Algoritums? Questions	1	426	September 21, 2022
Simple weekend project - maze game Demos and projects	1	815	February 2, 2020
Navmesh and dynamic environments Questions	6	569	April 28, 2023

Need help to find best pathfinding solution for my next project (tower defense game)

Related topics