Grid made using Arrays of ArrayLists

Thread view:

Veleek - 03 Dec 2005 19:47 GMT

Hello,

I'm looking to create a kind of grid with each time being made up of a
kind of bag (I was using ArrayLists) that I can use to add a series of
object do depending on their location in a field.

I'm using this method so I can efficiently determine which objects are
near to each other. I'd like to use this method to keep the algorithm
to O(n) as opposed to O(n^2).

What I've tried to do is make a 2-d array of ArrayLists that I
implemented with:
ArrayList[][] grid = new ArrayList[40][40];

Unfortunately, The arraylists don't seem to initialize themselves and I
just get a 2D Array of nulls. I've tried just making a 1D Array of
ArrayLists and it does the same thing and doesn't initialize.

Does anybody have any suggestions? I would also be willing to accept
any other ideas for maintaining a grid style listing like this. Though
keep in mind that the object will be moving around so it needs to be
possible to add and remove items from the Boxes/Bags. Please let me
know what you think.

- Ben Randall

Reply to this Message

Roedy Green - 03 Dec 2005 20:21 GMT

>I'm using this method so I can efficiently determine which objects are
>near to each other. I'd like to use this method to keep the algorithm
>to O(n) as opposed to O(n^2).

http://mindprod.com/jgloss/hangingmoss.html

Signature

Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Reply to this Message

Roedy Green - 03 Dec 2005 20:21 GMT

>Unfortunately, The arraylists don't seem to initialize themselves and I
>just get a 2D Array of nulls. I've tried just making a 1D Array of
>ArrayLists and it does the same thing and doesn't initialize.

see http://mindprod.com/gotchas.html#ARRAY

Signature

Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Reply to this Message

Veleek - 03 Dec 2005 20:27 GMT

Hi Roedy,

Thanks for the great reply time. But is the server currently down?
I'm getting Operation Timed Out errors when I try to follow the links.
Are there any possible mirrors or copies that I could get a look at?

Reply to this Message

Roedy Green - 03 Dec 2005 20:59 GMT

>Thanks for the great reply time. But is the server currently down?

My ISP is being less than helpful but he did say it was going to do
phase 2 of the upgrade this weekend. If all goes well in a few hours
it should be back up at a new IP and running 10 times faster.

Signature

Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Reply to this Message

Veleek - 04 Dec 2005 03:17 GMT

Roedy,

This was exactly the type of thing I was looking for. Though if you
don't mind I have a few things that I would like you to expand upon.

First of all, for determining which cell an object is in I'm using
this:

int xTile = (int)Math.round(Math.floor(pos.x/TILE_SIZE));

I don't really like having to have the cause and putting two
Math.rounds next to each other wasn't very nice either. Is there an
easier way to do this? You said in the article you linked me to, that
it can be done with:
"You can do this with a simple truncated division of the x and y
co-ordinate by the gridsize."

Second point, if you can expand upon the following paragraph a bit that
would be great. What I'd really like to know is, is there something
better to be using than ArrayLists? Would you recommend creating my
own stucture for something like this?

"Put all the points that fall in the same grid cell together on a
chain. You just go through all your points categorising them and adding
them to the head of the appropriate unidirectional chain for the
corresponding grid cell. You don't have to do all the points for a
given cell together."

Once again, thank you for your help, and kudos for the great site.

Reply to this Message

Veleek - 04 Dec 2005 03:29 GMT

Sorry Chris and Thomas,

I typed up the message and forgot to post it, then I left for a few
hours so I didn't notice your messages before I posted.

Just FYI Chris, your correct, that was the solution outlined on Roedy's
site.

Thomas, what did you mean by there is less need to directly use
reference arrays.

Also, the solution I discovered to Type my ArrayLists was:
ArrayList<JBoid>[][] grid = (ArrayList<JBoid>[][])new
ArrayList[40][40];

At least I think that's what I used. I ended up taking it out because
to be honest I wasn't worried with accidentally adding the wrong type
and was okay with casting the objects.

Reply to this Message

Thomas Hawtin - 04 Dec 2005 15:49 GMT

> Thomas, what did you mean by there is less need to directly use
> reference arrays.

Ths significant advantage of reference arrays over List, is that the
type information of the elements is kept in the former (more or less).
With generics that advantage disappears. All you are left with is a
slightly better syntax, an indication that you cannot structurally alter
the container and a tiny (usually negligible) performance improvement.

> Also, the solution I discovered to Type my ArrayLists was:
> ArrayList<JBoid>[][] grid = (ArrayList<JBoid>[][])new
> ArrayList[40][40];

That will add lint to your code. You can sweep it under the carpet with
@SuppressWarnings. But there is no need.

It's a pity that that technique is used in the implementation of
collections, IMO. Even there an object that matches the erasure, but not
the generic parameter, is forced.

> At least I think that's what I used. I ended up taking it out because
> to be honest I wasn't worried with accidentally adding the wrong type
> and was okay with casting the objects.

For my money, the main advantage of generics is about eliminating the
possibility of certain classes of bug, although that isn't a bad thing.
They are about documentation. Taken an instance at a time, casting might
make sense. Over any significant collection of code, I find untyped
collection a nightmare.

Tom Hawtin

Signature

Unemployed English Java programmer
http://jroller.com/page/tackline/

Reply to this Message

Veleek - 04 Dec 2005 20:37 GMT

Okay guys,

Just wanted to say thanks again for all your help and pointing me in
the right direction.

Reply to this Message

Roedy Green - 04 Dec 2005 06:00 GMT

>int xTile = (int)Math.round(Math.floor(pos.x/TILE_SIZE));
>
[quoted text clipped - 4 lines]
>"You can do this with a simple truncated division of the x and y
>co-ordinate by the gridsize."

if x and y are ints you can find the row and column as ints with:

row = y / gridheight;
col = x / gridwidth;

Signature

Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Reply to this Message

Roedy Green - 04 Dec 2005 06:02 GMT

>"Put all the points that fall in the same grid cell together on a
>chain. You just go through all your points categorising them and adding
>them to the head of the appropriate unidirectional chain for the
>corresponding grid cell. You don't have to do all the points for a
>given cell together."

The most efficient scheme would be to allocate two pointers in your
chain objects next and prev. Then to add an object you insert it at
the head of the chain in the usual way setting up the new object to
point to the old head object and the head pointer to point to the
newly added object.

Signature

Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Reply to this Message

Chris Smith - 03 Dec 2005 21:52 GMT

Roedy's site probably says this, but since it's down...

> Unfortunately, The arraylists don't seem to initialize themselves and I
> just get a 2D Array of nulls. I've tried just making a 1D Array of
> ArrayLists and it does the same thing and doesn't initialize.

Yep. A simple loop solves that:

for (int i = 0; i < grid.length; i++)
{
for (int j = 0; j < grid[i].length; j++)
{
grid[i][j] = new ArrayList();
}
}

Signature

www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

Reply to this Message

Thomas Hawtin - 03 Dec 2005 22:19 GMT

> What I've tried to do is make a 2-d array of ArrayLists that I
> implemented with:
> ArrayList[][] grid = new ArrayList[40][40];

You have created an array of arrays, and the arrays within them. These
subarrays will all have their elements initialised to null. So, your
initial problem is to loop through the elements and assign them a new
ArrayList, of appropriate capacity.

With the current version of Java (1.5), there is less need to directly
use reference arrays. Also arrays of generic types are not permitted.
You might consider using a List of Lists.

Tom Hawtin

Signature

Unemployed English Java programmer
http://jroller.com/page/tackline/

Reply to this Message

Grid made using Arrays of ArrayLists

Free Magazines