Pathfinding without predefined grid

Hello,
I´m learning Unity making a 2D top-down game. The map in this game is made from 8k*8k block grid. Each block id in the grid has coresponding prefab(all 1 meter square size) and walkability. I tried to customize some A* solutions to use it instead of checking for walkability by rays and such, but i failed. My question is: Is there an easy way to pathfind with A* algorhitm without generating grid of nodes, not having to generate new class for each tile? And as this is surely doable for somebody more advanced, would this even be more useful than generating like 20*20 grid around every NPC?
Thanks for any answers.

 

I'm not sure what you are asking. A* is basically a graph search. Graph searches are inherently node based.

There is no reason you can't generate nodes on the fly at runtime if needed. Nodes can be fairly light weight, all they need to store is the h-cost, g-cost, a reference to each neighbour and a reference to the previous node. (Sometimes adding in a reference to the nodes position can be valuable too, depending on your implementation).

 

This. Although there's another key piece to A* which is connections. Basically, every node can connect to another node or not.

Imagine brute forcing a maze... going down a path until the very end then finding another path to trace. That's what A* is fundamentally. You can define a maze with a grid, at places with turns (aka navmesh), or even a bunch of random nodes that aren't related in space.

A* assumes that the nodes are related in space so that a node closer to the end point has a higher chance of being on the right track. Conceptually, it's brute forcing a maze but going down the closer routes first.

Btw caching nodes might solve your problem of creating many new objects. When you no longer need a node, just send it into the cache.

Code (CSharp):

1. static readonly Stack<Node> nodeCache = new Stack<Node> ();
2. public static Node CreateFromCache () {
3.     return nodeCache.Count > 0 ? nodeCache.Pop () : new Node ();
4. }
5. public static void Cache (Node node) {
6.     nodeCache.Add (node);
7. }

It's probably not even worth it though, especially if the nodes are only generated at startup.

 

Thanks for your answers guys, guess I'll just have to learn more and write a system for my needs. My concerns were creating seperate node classes for each tile, which is 67108864 for the whole map, and when generating on runtime, the number of nodes I'd have to generate around NPCs. Thank you for the caching idea, I always connected it only with objects like bullets so it didn't come to my mind.

EDIT: I found Voxelmetric, 3D open-source project with tutorials, and it had really easy to understand A* code with little struct and no big grid generation in Start, I modified it to work in 2D and it's flawless! Sorry guys for bothering you with nooby questions.