Autor Wątek: Odcinek na gridzie przecięcie z siatką.  (Przeczytany 1003 razy)

Offline koirat

  • Użytkownik

# Listopad 23, 2012, 16:09:01
To wątek który może mi udowodnić użyteczność tego forum :)

Jedną z technik jaką stosuje do wykonanie bezkolizyjnego ruchu jest następujący algorytm.
http://lifc.univ-fcomte.fr/~dedu/projects/bresenham/index.html
Jest to modyfikacja algorytmu Bresenham która znajduje wszystkie komórki na siatce posiadające część wspólną z zadanym odcinkiem.

Problem tego algorytmu jest taki iż działa on jedynie gdy pozycje komórki podamy jako liczbę całkowitą.
Czy zna ktoś taką modyfikacje której będzie można podać dokładną pozycje na komórce.
Swoją drogą znalazłem coś takiego
http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html
a dokładniej "Simplifying, Round One"
Jednak zwraca on nieco inne wartości niż LineSupercover. W niektórych przypadkach zwraca mniej niż LineSupercover.

A jeśli ktoś zna algorytm w którym będzie można podać grubość linii to już w ogóle będę zobowiązany.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline koirat

  • Użytkownik

# Marzec 05, 2013, 20:49:44
Ok coś tam mi się swojego czasu udało wyrzeźbić. Pomyślałem że się podzielę.

źródło w C# i unity3d więc funkcje matematyczne będzie trzeba zmienić w wypadku innego zastosowania.

Algorytm działa tak: Podajemy dwie komórki na siatce. Lub dwa punkty na siatce. (zależnie od algorytmu). otrzymujemy listę wszystkich komórki przez które przejdzie odcinek je łączący.

Odcinek jest nieskończenie wąski, i nie ma opcji podania jego grubości.

Zaskoczyło mnie natomiast to iż algorytm na liczbach zmiennoprzecinkowych wydaje się być szybszy. Znikomo szybszy, ale spodziewałem się że będzie dużo wolniejszy.

Raczej stosować do nie ujemnych pozycji komórek. Do innych na własne ryzyko ;)

Pierwszy LineSupercover to ściągnięty i przerobiony na c# kod z internetu. (oparty na algorytmie Bresenham)
Działa tylko na liczbach całkowitych.

Drugi to moja radosna twórczość, oparty na niczym ;) algorytm któremu podajemy pozycje na siatce o znormalizowanej wielkości komórek. Innymi słowy (1.5,0.5) będzie to środek komórki którą mogli byśmy zaindeksować jako (1,0) gdybyśmy operowali na liczbach całkowitych. Naturalnie można podawać inne pozycje na komórce nie tylko środki.

Algorytm drugi jest trochę mniej dokładny w związku z działaniami zmiennoprzecinkowymi.

using System.Collections.Generic;
using UnityEngine;

public static partial class MathUtils
{

public static List<Cell> LineSupercover (int x1, int z1, int x2, int z2)
{
  int estmatedCount=Mathf.Abs(x1-x2)+Mathf.Abs(z1-z2);
  List<Cell> pointsList=new List<Cell>(estmatedCount);

  int i;               // loop counter
  int ystep, xstep;    // the step on y and x axis
  int error;           // the error accumulated during the increment
  int errorprev;       // *vision the previous value of the error variable
  int y = z1, x = x1;  // the LineSupercover points
  int ddy, ddx;        // compulsory variables: the double values of dy and dx
  int dx = x2 - x1;
  int dy = z2 - z1;
pointsList.Add(new Cell(x1,z1));
  //POINT (y1, x1);  // first point
  // NB the last point can't be here, because of its previous point (which has to be verified)
  if (dy < 0){
    ystep = -1;
    dy = -dy;
  }else
    ystep = 1;
  if (dx < 0){
    xstep = -1;
    dx = -dx;
  }else
    xstep = 1;
  ddy = 2 * dy;  // work with double values for full precision
  ddx = 2 * dx;
  if (ddx >= ddy){  // first octant (0 <= slope <= 1)
    // compulsory initialization (even for errorprev, needed when dx==dy)
    errorprev = error = dx;  // start in the middle of the square
    for (i=0 ; i < dx ; i++){  // do not use the first point (already done)
      x += xstep;
      error += ddy;
      if (error > ddx){  // increment y if AFTER the middle ( > )
        y += ystep;
        error -= ddx;
        // three cases (octant == right->right-top for directions below):
        if (error + errorprev < ddx)  // bottom square also
pointsList.Add(new Cell(x,y-ystep));
          //POINT (y-ystep, x);
        else if (error + errorprev > ddx)  // left square also
pointsList.Add(new Cell(x-xstep,y));
          //POINT (y, x-xstep);
        else{  // corner: bottom and left squares also
pointsList.Add(new Cell(x,y-ystep));
          //POINT (y-ystep, x);
pointsList.Add(new Cell(x-xstep,y));
          //POINT (y, x-xstep);
        }
      }
pointsList.Add(new Cell(x,y));
      //POINT (y, x);
      errorprev = error;
    }
  }else{  // the same as above
    errorprev = error = dy;
    for (i=0 ; i < dy ; i++){
      y += ystep;
      error += ddx;
      if (error > ddy){
        x += xstep;
        error -= ddy;
        if (error + errorprev < ddy)
pointsList.Add(new Cell(x-xstep,y));
          //POINT (y, x-xstep);
        else if (error + errorprev > ddy)
pointsList.Add(new Cell(x,y-ystep));
          //POINT (y-ystep, x);
        else{
pointsList.Add(new Cell(x-xstep,y));
          //POINT (y, x-xstep);
pointsList.Add(new Cell(x,y-ystep));
          //POINT (y-ystep, x);
        }
      }
pointsList.Add(new Cell(x,y));
      //POINT (y, x);
      errorprev = error;
    }
  }
return pointsList;
  // assert ((y == y2) && (x == x2));  // the last point (y2,x2) has to be the same with the last point of the algorithm
}



//includeAdditionalWhenDiagonal add additional two cells when moving throught corner from one cell to another
public static List<Cell> LineSupercover(float x1, float z1, float x2, float z2,bool includeAdditionalWhenDiagonal)
{
int estmatedCount= (int)(Mathf.Abs(x1-x2)+Mathf.Abs(z1-z2)) + 1;
List<Cell> pointsList=new List<Cell>(estmatedCount);

    float dx=x2-x1;
float dz=z2-z1;

float dzx=(float)(dz/dx);

int endCellX=Mathf.FloorToInt(x2);
int endCellZ=Mathf.FloorToInt(z2);

int cellX=Mathf.FloorToInt(x1);
int cellZ=Mathf.FloorToInt(z1);

pointsList.Add(new Cell(cellX,cellZ));

//point inside uniform cell of a grid
float octanX=x1 - Mathf.FloorToInt(x1);
float octanZ=z1 - Mathf.FloorToInt(z1);

while( !(cellX==endCellX && cellZ==endCellZ) ){

Cell nextCell = CellNextOctant(octanX,octanZ,dx,dz,out octanX,out octanZ);

if(includeAdditionalWhenDiagonal){
if(nextCell.x!=0 && nextCell.z!=0){

pointsList.Add(new Cell(cellX, cellZ + nextCell.z) );
pointsList.Add(new Cell(cellX + nextCell.x, cellZ) );
}
}

cellX+=nextCell.x;
cellZ+=nextCell.z;
pointsList.Add(new Cell(cellX,cellZ));

}

return pointsList;
}

public static Cell CellNextOctant(float x,float z,float dx,float dz,out float octanX,out float octanZ){

int addX=0;
int addZ=0;

if(dx==0 || dz==0) {

if(dx!=0){
addX = dx > 0 ? 1 : -1;
octanX = dx > 0 ? 0 : 1;
} else {
octanX=x;
}

if(dz!=0){
addZ = dz > 0 ? 1 : -1;
octanZ = dz > 0 ? 0 : 1;
} else {
octanZ=z;
}

return new Cell(addX,addZ);
}

float dzx=dz/dx;
float idzx=dx/dz;

float ddx = dx > 0 ? 1-x : -x;
float ddz = dzx*ddx;

float px = dx > 0 ? 1 : 0;

float pz = z+ddz;

if(pz >= 1){
addZ=1;
octanX=x + idzx * (1 - z);
octanZ = 0;

} else if(pz <= 0){
addZ=-1;
octanX = x + idzx * -z;
octanZ = 1;
} else {
octanX=0;
octanZ=0;
}

if(pz <= 1 && pz >= 0){

if(dx > 0){
addX=1;
octanX=0;
} else {
addX=-1;
octanX=1;
}

if(addZ > 0){
octanZ=0;
} else if (addZ < 0){
octanZ=1;
} else {
octanZ=pz;
}
}

return new Cell(addX,addZ);
}
}

cell
using UnityEngine;
using System.Collections;

public struct Cell {
public int x;
public int z;

public Cell(int x,int z){
this.x=x;
this.z=z;
}

public override string ToString (){
return string.Format ("Cell({0},{1})",x,z);
}

public static Cell operator +(Cell a,Cell b){
return new Cell(a.x+b.x,a.z+b.z);
}

public static Cell operator -(Cell a,Cell b){
return new Cell(a.x-b.x,a.z-b.z);
}

public static bool operator != (Cell a,Cell b){
return (a.x != b.x) || (a.z != b.z);
}

public static bool operator == (Cell a,Cell b){
return (a.x == b.x) && (a.z == b.z);
}

public override bool Equals (object obj)
{
if(!(obj is Cell))
return false;

Cell other=(Cell)obj;

return this.x == other.x && this.z == other.z;
}

public override int GetHashCode ()
{
int hashcode = 17;
hashcode = (hashcode * 23) + x;
hashcode = (hashcode * 23) + z;
return hashcode;
}

public bool IsNeighbour(Cell other,bool diagonalAllowed){

Cell diff=this-other;

if(diff.x < 0)
diff.x=-diff.x;

if(diff.z < 0)
diff.z=-diff.z;

if(diagonalAllowed){
if(diff.x == 1 && diff.z ==1)
return true;
}

return (diff.x == 1 && diff.z == 0) || (diff.x == 0 && diff.z == 1) ;

}

}