Algorithm to find distance to the closest?

[sciwizeh]

So, working on my ongoing Falling Sand Game project, I find that the best way to make the heat spread evenly is to use distances from heat sources. the problem is that the only way i can think to do that is brute force.

Here's a simplified version of my problem.

i have a 2D array such as:

1,2,3,4
5,4,3,5
1,3,3,2
2,3,5,6

So, if 3 is a heat source, then while looping through the arrays, how can i find out which 3 is the closest and how far away it is from the current position? ex: (1,1) is closest to the 3 at 1,3 with a distance of 2, but if everything can move in the array, the positions will not be known in advance.

Any Advice?

[Rashakil Fol]

The most obvious direct answer is to make a quadtree that keeps track of which quadrants contain 3s and which don't. Then zoom in on a given point from above, continuing to enter regions that contain 3s and are still candidates for the closest 3 to your given point.

You could also use some "fake" distance metric. For example, the distance from a heat source could be one plus the least distance from a heat source of one of your four or eight neighbors. (With one, heat propagates in squares, with the other, in diamonds, so I would just go with the former which is cheaper to compute.) A better "fake" distance metric would be to let each square be either 1 plus or sqrt(2) plus a neighbor's square's distance -- using sqrt(2) if the neighbor is diagonal. Pick the neighbor that minimizes your computed distance. With the latter method, areas of equal distance will form octagons around heat sources.

[sciwizeh]

Thanks for the advice, I'm not sure I understand what you mean about the "fake" metric system.

I just had another thought on how to go about doing this, again, I'm not sure about how to go about it.

My thought is to use the scan through all elements that I am already doing. during which when a '3' is found get a radial gradient of numbers and add them to the current numbers for heat.

The problem is I don't know how to make a radial gradient and I can't seem to find anything simple on a google search... any search I make with gradient returns vector gradients or gradient making tutorials for/or of programs.

[Lord Soth]

Hi,

I want to ask some questions. What are the other numbers signify ? Are they heat values or a discrete enumeration like wall, empty space, heat source, etc..

Also can you give us an estimate for the size of the real matrix. Because till a calculatable small number a polynomial or even exponantial time algorithm can perform faster than a sub-polynomial algorihm.

Also, what is the density of heat sources (cells with 3) in respect to number of cells. If the heat sources (or the affected 1 cells) are relatively rare on the whole grid, you can precompute some positional approximations for the rare cells.

Searching in a growing square/diamond fashion is a good idea as mentioned on the previous post.

Lastly, if the movement of objects in cells has a constant speed (i.e. 1 cell per time interval) you can use most of the calculations from previous frame and update it for the next with a smaller computation.

[sciwizeh]

i was simplifying the actual problem, really i have two matricies, one for what object is there and one for the heat value that is there, it's hard to say what the numbers really represent, because it is up to the user, with the click of a button it reloads the entire physics system with a new set of elements, and therefore heat sources based on a file. i have another matrix that detonates whether the pixel gives off heat, it's rather complicated... if you want to see the source i can provide a link, it's written in java, if you want to see the program itself you can find it at my site: matrixpeckham.googlepages.com

[Tech Tiger1]

Just go for: http://books.google.com/books?id=juuPxtSCg50C&pg=PA758&lpg=PA758&dq=Algorithm+to+find+distance+to+the+closest%3F&source=web&ots=TxO5lq6SB1&sig=R-y2SwJx700npLjc97dTNORrrLU&hl=en&ei=MR-USZDPKpWukAXQ-pC3Cw&sa=X&oi=book_result&resnum=1&ct=result#PPA750,M1

Thanks
Tech Tiger1