Jump to content
  • Advertisement
Sign in to follow this  
menyo

Do i really need to deep copy this?

This topic is 1504 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey,

 

I come from a C# and i'm trying to get my Astar implementation working on java for Android. Since Java is pass by value I need to make a copy of this Array[][] each time I request a path. This feels awkward for me and perhaps unnecessary.

 

So what i actually do in my Astar method, instead of iterating over a closed and open list many time, or putting new nodes into it in a ordered fashion I am creating a 2D map resembling my map in nodes. These nodes hold a open and closed boolean so all i need to do is check directly on this map if this tile belongs to the open/closed list, see move cost and if it is walkable. Instead of searching for it in a potential huge open list each time. I create this map when a new map is loaded, so with C# this actually got created only once.

 

Anyway, I did the same in Java but when I passed this NodeMap as a parameter it actually alters the base object instead of making a copy to work on. Now my (crude?) solution was to implement a constructor for my Node class so i can deep copy the complete NodeArray[][].

public Node(Node copy)
        {
            this.G = copy.G;
            this.H = copy.H;
            this.position = copy.position;
            this.parent = copy.parent;
            this.closed = copy.closed;
            this.open = copy.open;
            this.walkable = copy.walkable;
        }

And here i copy it, every time i need a path, i pass the actual Array[][] that needs to stay unaltered as nodeMapRef.

Node[][] nodeMap = new Node[nodeMapRef.length][nodeMapRef[0].length];
        for (int y = 0; y < nodeMapRef[0].length;y++)
        {
            for (int x = 0; x < nodeMapRef.length;x++)
            {
                nodeMap[x][y] = new Node(nodeMapRef[x][y]);
            }
       }

It really loses it's charm this way but i cannot think of a good way to handle this. And i can imagine if my map size grows and need much more paths this might slow things down significantly.

Share this post


Link to post
Share on other sites
Advertisement

There is no way around the deep copy problem.  If you pass references to objects around, then any change to the object it points to will change it everywhere.  But as you said, cloning the map every time seems wasteful.  Is there anyway to have two maps and just reset the path map to be the same as the base map instead of creating a new one every time?

 

I'm not that familiar with C# to know the  subtleties, but how did C# get away without doing a copy?  Seems like somewhere, some how, there had to be a copy made or the same thing would have happened.

Edited by Glass_Knife

Share this post


Link to post
Share on other sites

As to your C# question, it took me some time to look it up in all of my tests on pathfinding. But it seems I do re-initialize it every time as well. Since at the start of the pathfinding I know the open and closed flags should be always false and walkable flag does not change I just iterated the map and reset the flags before I request a path.

 

So creating a second NodeArray[][] and reset the NodeArray[][] i work on with that should be cheaper then iterating over it and resetting each flag "manually"? This is a simple solution, almost too simple :). One would think that behind the scenes the exact same thing happens or does just the memory pointer change?

Share this post


Link to post
Share on other sites

C# is also pass by value, as is c++.

I don't think you can pass the array without cloning it first in C#.

In C# you can easily implement deep copy by serializing an object graph using a binary serializer, and then deserialize the object graph to obtain a clone.

It's not a perfect solution, but at least it's a generic one, maybe you can do something similar in java ?

Share this post


Link to post
Share on other sites

I don't know if you are aware, but Java comes with the "jconsole" GUI tool that will let you profile the code and see which one is the fastest.  At this point it won't matter too much but it may in the long run.

 

http://docs.oracle.com/javase/7/docs/technotes/guides/management/jconsole.html

 

I have no idea how to profile stuff on Android.  It might be completely different.

Edited by Glass_Knife

Share this post


Link to post
Share on other sites

In C# you have value types and reference types where in Java you only have reference types apart from primitives. In some cases this can make a huge difference, but only if the types are in fact value types (structs)..?

 

In that case, you can just to something like Array.Copy() in C# to clone all the data, where in Java that would only clone the references. It would still be slow and inefficient, but at least it doesn't involve tons of allocations and garbage collections like I assume it will in Java.

Share this post


Link to post
Share on other sites
The clear and best answer - and this is very valid even in C++ - is to just use _different arrays_ for static/unchanging data versus dynamic data.

In A* for path-finding, most of your per-node data is of course baked into the map. It doesn't change. The node locations, masks/sizes, costs, etc. are part of the map and don't change for each execution of the algorithm.

The per-node state for each node does change.

You can easily separate your arrays such that your path-finding state keeps a reference to that unchanging data while keeping only the per-executation data in its own arrays, removing the need to copy all that data around.

On top of that, you can avoid having to initialize a lot of Nodes by using arrays of primitive data. e.g., you can just keep an array of ints for some of the state and an array of floats for other bits of state. This makes the allocation easier and - in a language like Java - is critical to getting good performance (since an array of objects in Java is not guaranteed or even likely to give you contiguous memory access patterns, but an array of primitives is). So you really want to replace your Node class entirely in favor of using separated arrays for each individual piece of primitive data for your path-finding. Some of those arrays can be shared and never need to be copied at all. Some can be reused between path-find executions and need to be cleared.

When then looking at these arrays, you might consider a "chunky" hierarchical or tiled approach. e.g. if each pathing execution is only likely to touch a small sub-rectangle of the total map, while clear an entire map-sized array of state data? Resizing the array frequently is also bad juju, but breaking the map into chunks and then only using and clearing an array for a chunk actually being inspected can save you a ton of CPU time and memory.

Short version: an array of Nodes is the wrong way to do good path-finding so it's not important if it's a pain to reinitialize or copy because you shouldn't be doing it.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!