I'm trying to write an algorithm in Java that does path finding with the brief that object and array instantiation is expensive, so I'm trying to avoid it as much as possible. Given this, I think it is fine to sacrifice a bit of performance to save on instantiation(primitives are fine). I would like to be honest here and say that this work is assesed, and I do want to do it myself (although it is more about coding style than anything else) so I'm just wondering if anyone can point me to a particular algorithm/variation of an algorithm that fits my brief, as I don't have a lot of experience with this. I'm looking at A* or IDA* at the moment, but they're not so good on the instantiation front. Any help is much appeciated, thanks

So you would be ready to sacrifice performance in order to avoid instantiation, the point of that being that you will save performance? This seems shady to me.

That being said, object and array instantiation in Java is very fast—about as fast as stack variables in C and C++. Of course, if you allocate a lot of objects, the garbage collector will perform a pass that may take some time, but if you manage your memory correctly (allocate a lot of small objects, use as few objects as possible at any time) you will end up with a pass that merely traverses and copies your currently used objects around.

Either way, read this.

But A* involves little instantiation anyway, so why be afraid of it?

Hi,
Thanks for your reply. Normally I'd be more than happy to instantiate objects, but this has been set as an exercise/challenge, so while there's nothing wrong with instantiating stuff, I'm still meant to avoid it where possible.
A* seemed like it would need a new instantiation for every new tile investigated, is this not the case? I thought it would look at a tile, calculate its heuristic, then need to instantiate/extend an object to store that information. Either that or have large empty structures bigger than you'd need, which is't very elegant.
If I've got the wrong end of the stick with A*, please correct me; I'd like to use it if it could be implemented to suite my needs.
Thanks again

The A* algorithm says nothing about when you instantiate objects, or how many objects you instantiate. Heck, even the notion of an object is just a language-specific implementation detail.

Let's get down to basics: What data structures do you need in A*? An OPEN priority queue. A CLOSED list or hash (hash is probably best). And a way to keep track of the parents of nodes -- a tree.

So how do you implement a priority queue, or a hash, or a tree, with a minimum of instantiation? From this point of view, your problem isn't about A*; it's about implementing these data structures efficiently in your language.

You can do a priority queue as a heap implemented with a fixed-length array (or use the doubles-in-size-when-it-gets-too-big strategy for a compromise) and some index arithmetic. You can trivially do a 1-1 hash with a fixed-size bitmap. You can represent a tree by simply giving each of your pre-allocated tiles a way to refer to a "parent." Et voila: No (or if you use the doubling strategy, very limited) instantiation as you run A*.

-----

From another point of view, you can choose a dead-simple pathfinding algorithm that requires much simpler data structures; i.e., Value Iteration, which for your problem requires nothing but a 2d array the size of your map. It's not a terribly efficient algorithm for this purpose, but it's easy, and it avoids instantiation (if that's all that matters, since this is an academic exercise).

-----

Finally: Is this problem about avoiding instantiation, or is it about "coding style?" It's easy to avoid instantiation; that's what my post above is about. But if this is really about emulating a particular coding style, then I'm the wrong guy to ask.

[Edited by - Emergent on April 10, 2009 11:00:52 AM]

Thanks again. One last thing - the brief also specifies:

"You must code your implementation in Java. You may not use any of the Java library functions in your solutions.
The remainder of your code must use only the basic Java datatypes."

I'm assuming by basic data types they mean primitives, but I'm not entirely sure exactly what constitutes a library function - would a priority queue count as a library function? If not I could presumeably implement my own.

Perhaps it means minimal instantiation DURING the execution of the algorithm ? (since this would hamper the efficiency of the search).

The solution would be to pre-allocate all the memory for nodes (i.e. build a node bank) before hand, taking the performance hit once upon program startup. Then you can just request a node from the node bank whenever needed?. That way during the algorithm youd be able to grow new nodes whenever needed, without having to actually instantiate any new objects.

Effectively you'd be sacrificing a chunk of memory to do this, but in my experience, it doesnt sound like itd be any kind of problematic amount. Just allocate it first, will give you far better performance during the search. Plus you can gain even further, from increased cache efficiency if you do it right.

Quote: Original post by NovaBlack
The solution would be to pre-allocate all the memory for nodes (i.e. build a node bank) before hand, taking the performance hit once upon program startup. Then you can just request a node from the node bank whenever needed?. That way during the algorithm youd be able to grow new nodes whenever needed, without having to actually instantiate any new objects.

In java, this is a performance suicide. Trust the generational GC, or work along with it, do not fight against it.

If your state space already exists as a graph (as is typically the case for path finding as opposed to 'search' more generally) then you can use members within those nodes to represent the search instead of having to create a parallel set of search nodes.

Depending on your brief, the simplest solution would be a depth-first search. The first step would be to guard against the possibility of infinite cycles. If you can see how that would work, extending the system to a different search algorithm while keeping allocations minimal should not be too difficult.

You can actually do the tree as an array too. As you walk through the nodes, store the node that you came from in the Parent array so that you can walk back through it. In C++, I've got the following structures. The code isn't as clear as the tree based structure, but it does no allocations after the initial one. In my case, it's a static variable, so it's initialized at startup. It does take up more space, but it does no allocations and is blazing fast.

bool CL[H_BORDER+1][V_BORDER+1]; //Closed List
bool OL[H_BORDER+1][V_BORDER+1]; //Open List
unsigned short G[H_BORDER+1][V_BORDER+1]; //G
shortPoint parent[H_BORDER+1][V_BORDER+1]; //Parent - to find the path
priorityQueue[H_BORDER*V_BORDER+4];

I can't find where I originally saw this idea but it should not be difficult to program, although getting all the details right is a pain.