Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm trying to implement flowfield navigation, as described in http://grail.cs.washington.edu/projects/crowd-flows/ but I can't understand how the Density Function in Figure 4 of the paper is supposed to handle unit radius.

Has anyone ever implemented that and can provide more information?

This is the part in question:

enter image description here

Their algorithm seems to be using only 4 cells, pointing to the lower left of the unit, so is this some kind of kernel that needs to be applied multiple times?

Thanks.

share|improve this question
    
Could not add more relevant tags because of reputation level. –  sharvey Mar 31 '13 at 19:37
add comment

1 Answer

up vote 3 down vote accepted

No, it's not a "kernel that needs to be applied multiple times". You just apply the formulas as written, once.

It's kind of a weird rule, though, and not very clearly described. Let me try to clarify it a bit:

  • First, find the four cells whose shared corner is closest to the unit. The unit will contribute a non-zero amount of density only to those cells. Call those cells A, B, C and D as in figure 4(b).

  • Let Δx and Δy be the horizontal and vertical distance of the unit from the center of cell A, measured in units of one cell width/height.

  • Let ρA = min(1−Δx, 1−Δy)λ, ρB = min(Δx, 1−Δy)λ, ρC = min(Δx, Δy)λ and ρD = min(1−Δx, Δy)λ, as described in the paper.

  • Let the unit contribute ρA density to cell A, ρB density to cell B, ρC density to cell C and ρD density to cell D.

As I said, the rule is kind of weird, and I have no obvious geometric interpretation to offer for it. It does, however, satisfy the expected properties that:

  • When the unit is exactly in the middle of any cell X, then (regardless of which of A, B, C or D we choose X to be) it contributes 1λ = 1 unit of density to cell X and 0 units of density to any other cell.

  • When the unit is exactly at the corner of four cells, it contributes (1/2)λ units of density to each of the four cells (and nothing to any other cell, by definition).

However, note that, using this rule, the total amount of density contributed by a unit to all cells is not constant, not even if λ = 1. In particular, when the unit is exactly at the midpoint of the edge between two cells, it contributes (1/2)λ units of density to those two cells, and nothing to any other cell. Thus, calling the resulting value a "density" seems a bit misleading.


Edit: Another way of writing the formulas for ρA, ρB, ρC and ρD, which may make the symmetry of the definitions more apparent, is to define dX = max( |x − xX|, |y − yX| ) as the chessboard distance of the unit at (x, y) from the center of the cell X at (xX, yX), measured in cell widths/heights. Then, for any cell X,

  • ρX = 0 if dX ≥ 1, and
  • ρX = (1 − dX)λ otherwise.
share|improve this answer
    
I don't understand the reason why the bottom left cells adjacent to the one the agent is in should receive density value while the top right ones should not. –  sharvey Apr 1 '13 at 2:35
    
@sharvey: Because in the picture, the agent is below and to the left of the center of the cell it is in. –  Ilmari Karonen Apr 1 '13 at 7:30
    
Ah, it makes sense. But just to be clear, the radius of the unit has nothing to do with the density calculation, right? –  sharvey Apr 1 '13 at 16:26
    
Right, there doesn't appear to be any "radius" in the formulas you quoted that could enter into those calculations. –  Ilmari Karonen Apr 1 '13 at 23:01
    
I'm not closer to actually implementing it, but thanks for the answer. Guess I'll read the paper again. –  sharvey Apr 2 '13 at 2:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.