Java Bresenham 线到圆周上的点

Question

我正在尝试为 2D 方 block 游戏编写一个闪电引擎。与大多数游戏一样，我在 map 上有一个 map [][]和一个光照贴图[][]。没什么特别的。从一个光点，我在灯光范围内画一个圆圈，并尝试将布雷森纳姆线绘制到圆圈上的点。由于某种原因，我的 Bresenham 算法并不完美，我添加了一张图像 它的。为什么布雷森汉姆线算法会跳过一些对角坐标(例如从点 20,20 到 13,14 和 14,13 跳过。)我认为误差计算是错误的。我使用 set 来避免数组中的重复。圆形算法工作正常，在数组中我得到了正确的值。图中还有一个问题:在某些情况下，水平线和有时垂直线也错误。我认为这也是布雷森汉姆的错误。我正在尝试一些调试 ，它显示了布雷森汉姆的错误。白色立方体是圆周上的点，红色通过布雷森汉姆线算法添加到光照贴图中，有一座山阻挡了光线(它工作完美)并且我的小 map 已启用。我添加了更多图像:

import java.awt.geom.Point2D;
import java.util.HashSet;

public class PointLight {

Handler handler;
public float x,y;
private int plx,ply;
public int radius,intensity;
public static Point2D.Double pnt;
public static HashSet<Point2D> circpoints;
public static HashSet<Point2D> bline;
public PointLight(float x,float y,int radius,int intensity,Handler handler) {
    super();
    this.x=x;
    this.y=y;
    this.radius=radius;
    this.intensity=intensity;
    this.handler=handler;
    circpoints = new HashSet<Point2D>();
    bline = new HashSet<Point2D>();
    pnt=new Point2D.Double();
}

public void tick() {
    //visibility for rendering process (1000 is for range, to avoid sudden light emitting)
    if (x > Game.camera.getX()-1000 && x < Game.camera.getX()+Game.Windoww+1000 && y > Game.camera.getY()-1000 && y < Game.camera.getY()+Game.Windowh+1000) {
        if (!Game.visiblepointlight.contains(this)) Game.visiblepointlight.add(this);
    } else {
        if (Game.visiblepointlight.contains(this)) Game.visiblepointlight.remove(this);
    }

    //reset visible lightmap
    for (int i=(int)((Game.camera.getX()-1000)/Game.tilesize);i < (int)((Game.camera.getX()+1000+Game.Windoww)/Game.tilesize);i++) {
        for (int j=(int)((Game.camera.getY()-1000)/Game.tilesize);j < (int)((Game.camera.getY()+1000+Game.Windowh)/Game.tilesize);j++) {
            if (i > 0 && i < Game.tiles && j > 0 && j < Game.tiles) Game.lightMap[i][j]=0;
        }
    }

    //set lights
    for (PointLight pli : Game.visiblepointlight) {
        bline.clear();
        circpoints.clear();
        Lightcalculate(pli);
    }

}

public void Lightcalculate(PointLight pl) {

    plx=(int)(pl.x)/Game.tilesize;
    ply=(int)(pl.y)/Game.tilesize;

    PointsOnCircumference(plx,ply,pl.radius);
    for (Point2D circp : circpoints) {
        bresenhamsLine(plx,ply,(int)circp.getX(),(int)circp.getY());

        for (Point2D plotl :bline) {
            double mult = Game.AmbientLight+(pl.intensity / PointDistance(plx,ply,plotl.getX(),plotl.getY()))/(Game.tilesize*2);
            //working but no brightness addition:
            //if (mult >1) mult=1;
            //Game.lightMap[(int) plotl.getX()][(int) plotl.getY()] = mult;
            Game.lightMap[(int) plotl.getX()][(int) plotl.getY()] += mult;
            if (Game.lightMap[(int) plotl.getX()][(int) plotl.getY()] > 1) Game.lightMap[(int) plotl.getX()][(int) plotl.getY()]= 1;
        }

    }
}

private double PointDistance(double x1, double y1, double x2, double y2) {       
    return Math.sqrt((y2 - y1) * (y2 - y1) + (x2 - x1) * (x2 - x1));
}

private void PointsOnCircumference(int x0, int y0, int radius)
{
    int x = radius-1;
    int y = 0;
    int dx = 1;
    int dy = 1;
    int err = dx - (radius << 1);

    while (x >= y) {
        pnt.setLocation(x0 + x, y0 + y);
        circpoints.add((Point2D) pnt.clone());
        pnt.setLocation(x0 + y, y0 + x);
        circpoints.add((Point2D) pnt.clone());
        pnt.setLocation(x0 - y, y0 + x);
        circpoints.add((Point2D) pnt.clone());
        pnt.setLocation(x0 - x, y0 + y);
        circpoints.add((Point2D) pnt.clone());
        pnt.setLocation(x0 - x, y0 - y);
        circpoints.add((Point2D) pnt.clone());
        pnt.setLocation(x0 - y, y0 - x);
        circpoints.add((Point2D) pnt.clone());
        pnt.setLocation(x0 + y, y0 - x);
        circpoints.add((Point2D) pnt.clone());
        pnt.setLocation(x0 + x, y0 - y);
        circpoints.add((Point2D) pnt.clone());

        if (err <= 0) {
            y++;
            err += dy;
            dy += 2;
        }

        if (err > 0) {
            x--;
            dx += 2;
            err += dx - (radius << 1);
        }
    }
}

private void bresenhamsLine(double x1,double y1,double x2,double y2) {
    double dx = Math.abs(x2 - x1);
    double dy = Math.abs(y2 - y1);

    double sx = (x1 < x2 ? 1 : -1);
    double sy = (y1 < y2 ? 1 : -1);

    double error = dx - dy;

    double x = x1, y = y1;

    while(1==1)
    {
        if ((int)x < 0 || (int)y < 0 ) break;
        if ((int)x >= Game.tiles || (int)y >= Game.tiles ) break;
        pnt.setLocation(x,y);
        bline.add((Point2D) pnt.clone());
        if (Game.map[(int)x][(int)y] >= 0.8) break; //light blocker

        if(x==x2 && y==y2) { break; }

        double e2 = 2 * error;

        if(e2 >= -dy) { error-= dy; x+= sx; }
        if(e2 <= dx) { error+= dx; y+= sy; }
    }
}
}

Answer 1

我想出了如何以其他方式生成阴影灯。它更简单并且 100% 有效。这是点光源瓷砖闪电的代码:

import java.awt.Point;
import java.util.HashSet;
import java.util.Random;

public class PointLight {

Handler handler;
public int x,y;
private int plx,ply;
public int radius,intensity;
public static Point pnt;
public static HashSet<Point> circpoints;
public static HashSet<Point> bline;
public GameObject BoundToObject;

public PointLight(int x,int y,int radius,int intensity,Handler handler) {
    super();
    this.x=x;
    this.y=y;
    this.radius=radius;
    this.intensity=intensity;
    this.handler=handler;
    circpoints = new HashSet<Point>();
    bline = new HashSet<Point>();
    pnt=new Point();
}

public PointLight(GameObject GamObj,int radius,int intensity,Handler handler) {
    super();
    this.BoundToObject=GamObj;
    this.x=(int) GamObj.getX();
    this.y=(int) GamObj.getY();
    this.radius=radius;
    this.intensity=intensity;
    this.handler=handler;
    circpoints = new HashSet<Point>();
    bline = new HashSet<Point>();
    pnt=new Point();
}

public void tick() {
    Random rnd;

    rnd=new Random();
    x+=rnd.nextDouble()*4;
    y+=rnd.nextDouble()*4;

    if (BoundToObject != null) {
        x=(int) BoundToObject.getX();
        y=(int) BoundToObject.getY();
    }

    //visibility for rendering process (200 is for range, to avoid sudden light emitting)
    if (x > (int)Game.camera.getX()-200 && x < (int)Game.camera.getX()+Game.Windoww+200 && y > (int)Game.camera.getY()-200 && y < (int)Game.camera.getY()+Game.Windowh+200) {
        if (!Game.visiblepointlight.contains(this)) Game.visiblepointlight.add(this);
    } else {
        if (Game.visiblepointlight.contains(this)) Game.visiblepointlight.remove(this);
    }

    //reset visible lightmap
    for (int i=(int)((Game.camera.getX()-200)/Game.tilesize);i < (int)((Game.camera.getX()+200+Game.Windoww)/Game.tilesize);i++) {
        for (int j=(int)((Game.camera.getY()-200)/Game.tilesize);j < (int)((Game.camera.getY()+200+Game.Windowh)/Game.tilesize);j++) {
            if (i > 0 && i < Game.tiles && j > 0 && j < Game.tiles) Game.lightMap[i][j]=Game.AmbientLight;
        }
    }

    //set lights
    for (PointLight pli : Game.visiblepointlight) {
        bline.clear();
        circpoints.clear();
        Lightcalculate(pli);
    }

}

public void Lightcalculate(PointLight pl) {

    plx=pl.x/Game.tilesize;
    ply=pl.y/Game.tilesize;

    RayCast(plx,ply,pl.radius);
        for (Point bln :bline) {
            double mult = (pl.intensity / PointDistance(plx,ply,bln.x,bln.y))/(Game.tilesize*3);
            if (Game.lightMap[bln.x][bln.y] < mult) Game.lightMap[bln.x][bln.y] =     mult;
            if (Game.lightMap[bln.x][bln.y] > 1) Game.lightMap[bln.x][bln.y]= 1;
        }
}

private void RayCast(int xcord,int ycord,int range) {

    double angle = 0;
    int rays=range*10+1;

    for (int i=0; i<rays; i++) {
        angle += 2 * Math.PI / rays;
        for (int j=0;j<range;j++) {
            double xx = xcord+Math.sin(angle)*j;
            double yy = ycord+Math.cos(angle)*j;
            if ((int) xx <= 0 || (int) yy <= 0 || (int) xx >= Game.tiles-1 || (int) yy >= Game.tiles-1 ) continue;
            if (Game.map[(int) xx][(int)yy] >= 0.8) break;
            Point dir = new Point((int) Math.round(xx),(int)Math.round(yy));
            bline.add(dir);
        }
    }
}

private double PointDistance(int x1, int y1, int x2, int y2) {       
    return Math.sqrt((y2 - y1) * (y2 - y1) + (x2 - x1) * (x2 - x1));
}
}