koobas.hobune.stream
Grid Generation
I am developing a pathfinding system for a game. It works, it's clean, and fast. It's works of a grid. Now I am going back to try and speed up my grid generation. As now I am instantiating a number of nodes and placing them. I need it this way so I can select individual nodes. Problem is if I generate a grid bigger than 32x32 unity hangs, a grid that is 100x100 pauses unity for at least 2 minutes. Anyway I can generate a grid of that size with little to no slow up, or at least unity not hanging until it is done.
for(var y : int = 0; y < gridSizeZ; y++){
for(var x : int = 0; x < gridSizeX; x++){
pos = Vector3(parentObj.transform.position.x + x,parentObj.transform.position.y,parentObj.transform.position.z + y) * gridSpacing;
clone = Instantiate(nodeObject.gameObject,pos,parentObj.transform.rotation).GetComponent(PathNode);
clone.SetRadius(nodeRadius);
graphNodes.Add(clone);
clone.graphID = this.GetInstanceID(); //Tell the node which graph it belongs to
clone.iD = this.GetInstanceID()+clone.GetInstanceID(); //Give Node an ID
clone.gameObject.name = clone.iD.ToString();
clone.transform.parent = parentObj.transform;
//Check Right
clone.CheckForNeighbor(Vector3.right,(gridSpacing *2));
//Check Left
clone.CheckForNeighbor(-Vector3.right,(gridSpacing *2));
//Check Up
clone.CheckForNeighbor(Vector3.forward,(gridSpacing *2));
//Check Down
clone.CheckForNeighbor(-Vector3.forward,(gridSpacing *2));
//Diagonals
clone.CheckForNeighbor(Vector3(1,0,1),(gridSpacing *2));
clone.CheckForNeighbor(Vector3(-1,0,-1),(gridSpacing *2));
clone.CheckForNeighbor(Vector3(-1,0,1),(gridSpacing *2));
clone.CheckForNeighbor(Vector3(1,0,-1),(gridSpacing *2));
}
scanProgress += progressPer;
}
//SET RADIUS FUNCTION
function SetRadius(rd : float){
transform.GetComponent(SphereCollider).radius = rd; size = rd*.5;
}
//Check Neighbor
function CheckForNeighbor(direction : Vector3,length : float){
var hitObj : RaycastHit;
var nodeObj : PathNode;
if(Physics.Raycast(transform.position,direction,hitObj,length,1 << 17)){ // Only Certain Path Layer
nodeObj = hitObj.transform.GetComponent(PathNode);
if(nodeObj.graphID == this.graphID){//Node we found is in our graph
AddNeighbor(nodeObj); nodeObj.AddNeighbor(this);
}
}
}
Can you show us your code for generating your grid? $$anonymous$$aybe we can help you to find what can be changed for the better.
I am not home to pull the code. So when I get back I will post the grid code. But what I am doing is two nested for loops followed by a single loop. In the nested loop I instantiate a node to position, add it to a list, parent it, set collider radius. Then I loop through all the nodes to get their adjacent nodes. But I just realized I can void the last loop and just check for adjacent nodes during instantiation loop.
Everything is happening in that loop! First thoughts were the instantiate and GetInstanceID, but it also depends on what is happening in SetRadius and also CheckForNeighbor (hope there's no .magnitude in there!). For a first suggestion, do all your calculations first, then in a new loop, cycle through the array and instantiate then. It's ok, when learning meshes I instantiated alot of spheres at vertex points so I could see I got the calculations right. Just think this may be one lag. If there are Debug in the other functions called then this also really slows down if you don't include some kind of yield after the debug log. Just 2 things that will jam up the process.
I think the general answer here is going to be "there has to be a better way"
(after the other functions were added) .... and a GetComponent in both the other functions! You seriously need to look at what you're doing, and find a better way, sorry.
I'm just saying, for 100x100 times, you have 1 instantiate and 9 GetComponents (and 2 GetInstanceID)
I have included the set Radius & Neighbor check. $$anonymous$$aybe the issue is that i am using physical nodes, rather than creating instances of a "node" class. If i do change I will need a way of finding neighbors & figuring out what node the player & ai are currently touching without scanning the whole grid
Under normal circumstances, using a grid for A* you wouldn't need to create objects. I would use either a position or a Rect instead. But maybe you need actual grid with objects in your project?
Just generally looking at the code, I feel that the "CheckForNeighbor"-function is unecessary. If you want to know which neighbours a node has, you can more easily check it using the knowledge how long and wide the list is.
ex.
var gridSizeX = 10;
var gridSizeZ = 10;
var totalGridSize = (gridSizeX * gridSizeZ);
for(var y : int = 0; y < gridSizeZ; y++)
{
for(var x : int = 0; x < gridSizeX; x++)
{
// Create clone and set its properties and whatnots...
// Get node neighbours
var thisNodeIndex = (y * gridSizeX) + x;
var downNeighbourIndex = (thisNodeIndex - gridSizeX);
var upNeighbourIndex = (thisNodeIndex + gridSizeX);
var leftNeighbourIndex = (thisNodeIndex - 1);
var rightNeighbourIndex = (thisNodeIndex + 1);
if(upNeighbourIndex >= 0)
{
// save neighbour index or object
}
if(downNeighbourIndex < totalGridSize)
{
// save neighbour index or object
}
if(leftNeighbourIndex >= 0)
{
// save neighbour index or object
}
if(rightNeighbourIndex < totalGridSize)
{
// save neighbour index or object
}
// add created clone to list...
}
}
Obviously some indices/objects doesn't exist when doing the check since they arent created (yet), so thats why I would save the index instead of the actual object.
This is just a example code I wrote fast without testing or optimizing, so it might not be functional, but it gives an idea of what I mean. Hopefully :-)
Good luck!
Thank yo! that is what i am doing now using a multi-dimensional array and a pathnode class. no instantiation,or complex check neighbor, just storing vector offset and array indexes. one problem i would have with this approach is how would i track ai & player position (nearest nodes) without continually scanning grid. Before i was using collision checking with the physical nodes.
Well, I think checking collision on physical nodes continually would be, as equal or maybe even more expensive, than run through a list (remember to exit the loop as soon as you found the right node!).
Using A* you should have a closed list with the nodes the object is using and that list is shorter than the grid orginal list.
If you aren't using the A* then maybe you don't need to scan the grid every frame to save some work.
ok i must have mistyped. ai Players & main user have a class that does a physics overlap-sphere on their current position with a layer-mask to only check for nodes. the actual nodes are not making the check it would be 10000 nodes doing physics constantly versus 10 characters. In the same aspect on avg cost doing a scan of all nodes to do a figure out which node the user is next to would be ---> O(numberofusers numberofnodes/2) = with 10 users and 10000 nodes = 10 500 = Expensive. I get what you mean by closes list and yest i am using a*..but this could only work for ai not the main-player which does not use the pathing system so i would still need to know which node the player is closest to
Ok. $$anonymous$$aybe you can do something like this :
At startup you get the node (and its index) where all individual player is standing. $$anonymous$$aybe Run through the loop once but check all players at the same time to avoid running the loop once per player.
And each update/frame, you check the player towards this node that you have currently stored. The check can include if the player is closer to this node or to any of its neighbour nodes, and update the current node accordingly. This should shorten the check for you.
So that would be 10 users checking maximum 5 nodes each = 50 nodes per frame.
ok i see what you mean. I was able to do use the multidim array and grid generates in less than a second now. so issue resolved. Now i just have to re-integrate everything. i will report on if your solution was quick enough, or something else i used.
i'm not trying to be dispiriting but is there a reason your not using the established pathfinding solutions?
NavMesh A* etc?
I mean fast pathfinding code isn't exactly something you stumble apon. :P
If your doing it because you'd rather have your own I guess so it's just that I mean i've no idea how to create unity or nividia phsyx or a number of other highly technical specialized set of code functions. That's why I leave it to the experts. :P
You could spend the next month coding that and it'd be way slower than the implementations already available out there with less functionality.
As a response,and not being snarky, but with that kind of attitude no one would ever innovate anything, or re-innovate the wheel & make it better. But to answer your question, i am developing a project and i want the entire project in house. I am a code enthusiast so i enjoy the challenge and do not want to wait for another individual to work on their project for me to update $$anonymous$$e with features(and i do not want to spam a feature request forum).if i did use another's pathing the geek in me would eventually want to make my own, so there is no point in wasting time learning others' code. $$anonymous$$y implementation is fast with avg computation time of .001 ms for paths of 38+ nodes. I am using 1. my own $$anonymous$$ heap, 2. dictionary 3. hashtable to keep all operations O(1)-O(logn) all in unity-script (will port to c# once i get it working). also most packages out there do not support multifloor grid-graphs (easily) & my implementation does it easily. But most importantly i am creating this so other people that i work with can utilize a system that is built in house. Plus its just fun to overcome a difficult task. :)
You get the source code with the free A* you can add your own features. your implementation is much slower than free A* which searches 1k nodes per millisecond. If you enable multi threaded support it can search 4.5k nodes with a 4 core proccessor.
It supports multifloor grid graphs
Don't get me wrong the A* algorithm already existed and so it was remade for unity and improvements were probably made during the reinvention etc.
Reinventing to improve is fine if that is your project. But your project is a game not a pathfinding algorithm. I mean you didn't re-invent a program$$anonymous$$g langauge or a game engine. :P You used what was already supplied.
I'm only saying this because I think it would suck for you personally if you ended up spending months on a pathfinding algorithm ins$$anonymous$$d of on the game and didn't get as many features into the game.
And what if your algorithm isn't efficient enough because you add more agents or nodes, you'd have to dump it all for the A* so you could have a game that had a playable framrate?
It's just that in highly specialized fields its best to leave it to the experts. People often try to create there own custom encryption algorithms, the result is stuff that is far less secure than using the universal standards of encryption. You can try and create your own physics simulations using transform and functions but its going to be way worse that trusting nvidia Physx.
If it works it works but remember there are also downsides to trying to a master of all. :P $$anonymous$$onths spent on pathfinding aren't spend on other features or code.
Well i am not making a game. This is the last thing i am focusing on in my project. I still have to make improvements but i am willing to spend a month on it, it would be another thing if i was program$$anonymous$$g illiterate and had no knowledge of data structures, run complexities, other search & sort algorithms,etcs. I want to learn so i can be an "expert". For instance path-finding is subjective in a way by the way you can calculated heuristics & deal with tie-breaking, path smoothing, and dynamic obstacle avoidance. I want a solution that is molded for my projects & can handle multi-floor graphs + graph linking methods, dynamic obstacles(reason why my implementation is slower as i scan each node for obstacles before i add it to open list). Anyway i don't want to be a developer that does not know exactly what is going on and know how to alter every piece of code in any of his projects. Don't get me wrong i used A* project to make & publish an iOs fps last year, it is a great package, and i was able to learn other things while using it. now it is time for me to tackle pathfinding, put it all together and i will have a great engine i can use for any project in the future. Sorry for the long winded response. :) i am a nerd at heart so i get passionate with subjects of such
nope A* is dynamic collision detection so it scans too. :P
600 agents with randomly placed obstactles spawning every few tenths of a second http://www.youtube.com/watch?v=htoen7x3LuQ
$$anonymous$$y guess is you should look at the source code for node generation/storing on the A* program for a faster implementation of node generation.
I will note that they use Cached implementation.
If each level starts out the same, take the time to spend 2 $$anonymous$$utes yourself calculating each levels nodes and then store that array with the scene, Then you can retrieve that at the start of the scene from then on with no hang/load time.
This is exactly what i'm trying to do but I have no idea how to store and load my array. I'm not asking for code, but a point in the right direction for how to do this would be greatly appreciated.
$$anonymous$$y array is 3d and stores 9,375,000 nodes. So it takes several $$anonymous$$utes to generate.
