# Slick Forums

Discuss the Slick 2D Library
 It is currently Fri Jan 24, 2020 10:29 am

 All times are UTC

 Page 1 of 1 [ 10 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Physical queries for the math challengedPosted: Sun Aug 10, 2008 5:00 am
 Oldbie

Joined: Tue Jun 17, 2008 5:11 pm
Posts: 336
I thought I'd share something I've written with y'all. It's an approach to collision detection I adopted when I wrote my last game, Forte. This is the first article of two which describes how to build the basic data object and perform basic collision detection.

I think this article is ideally suited for the programmer who is weak at math and wishes to write a game with physical queries such as ray casting to support various AI operations. I've managed to get pretty far without vector math and very simple information about collisions; I wrote this tutorial to illustrate how to do complex things without implementing complex math.

Top

 Post subject: Posted: Sun Aug 31, 2008 3:09 am
 Oldbie

Joined: Tue Jun 17, 2008 5:11 pm
Posts: 336
Hi again, sadly I haven't had much time lately to do real game programming but I have found some time to write about game programming. I wanted to share my second article in this series (and most likely the last). This one deals with ray casting a powerful technique which is useful for programming path finding and game AI among other things. You can find the article here http://anotherearlymorning.com/blog/physical-queries-for-the-math-challenged-ray-casting.

_________________
My website about game development http://anotherearlymorning.com

Top

 Post subject: Posted: Mon Sep 01, 2008 9:41 am
 Regular

Joined: Sun Feb 24, 2008 6:31 pm
Posts: 163
Location: UK
Nice one manunderground.

I checked out your articles which are very good and then also went through the tutorial you referenced as well.

I played with very simple raycasting a while ago and your article plus the tutorial got me thinking about doing something with it again. I ran through the tutorial this evening and created a slick version of a simple raycaster which can be seen here.

I'm just working on some texture mapping to make it a little more exciting. I was impressed with the speed I could get and I think it would be cool to create something along the lines of W3D. Very 1990s I know, but in terms of 3D its about as good as I think I'd get

MikeD

_________________
Work In Progress:
Atic Atac Remake
MegaBlast (First Slick Game I started)

Top

 Post subject: Posted: Mon Sep 01, 2008 1:33 pm

Joined: Tue Jun 03, 2008 5:13 pm
Posts: 38
Nicely written article. I'll be sure to come back to it the next time I need to implement some of that stuff. I think people really read and appreciate these kinds of sort of low leve/sort of high level tutorials, so keep it up

@miked - very cool! I'm also impressed with the speed (although I guess wolf32 ran okay on my old 286, so I shouldn't be too surprised)

Top

 Post subject: Posted: Mon Sep 01, 2008 3:59 pm
 Regular

Joined: Sun Feb 24, 2008 6:31 pm
Posts: 163
Location: UK
you are correct twood, given what W3D and Duke Nukem 3D were doing on a 286 with this technique, the basics I have on a 2.4Ghz Core 2 Duo should not be surprising. I think I was more surprised that given my bad Math skills and lack of understanding of a lot of what I implemented on the Math side, it seems to be working ok

We shall see how it looks when I have worked out the texture mapping, rendering a ceiling and floor and maybe even sprites

I don't necessarily see this ending up as a complete project, but is a fun 1990 tech demo at least.

MikeD

_________________
Work In Progress:
Atic Atac Remake
MegaBlast (First Slick Game I started)

Top

 Post subject: Posted: Mon Sep 01, 2008 4:57 pm
 Oldbie

Joined: Tue Jun 17, 2008 5:11 pm
Posts: 336
Have to say Mike that is really cool! I am actually going to investigate integrating Box2d w/ Slick since it looks like it supports ray casting out of the box (at least on if the forum is to be trusted). I was thinking I'd use that to create a game w/ real time shadows, using ray casting to determine where the shadows fall. If things don't work out I'll have to pilch some code from this awesome demo! I'm really glad you guys have found my stuff helpful! When I started game programming I couldn't believe that there was no information for some of these things so I'm trying to leave a trail behind for others.

_________________
My website about game development http://anotherearlymorning.com

Top

 Post subject: Posted: Fri Sep 12, 2008 9:31 am

Joined: Fri Oct 05, 2007 9:00 pm
Posts: 51
Location: japan
@miked

any chance raycaster is opensource ? or somehow publicly available..
i would need to create a kind of similar project, that could be good source of information..

anyway, nice work

Top

 Post subject: Posted: Fri Sep 12, 2008 9:40 am
 Regular

Joined: Sun Feb 24, 2008 6:31 pm
Posts: 163
Location: UK
Hi keisangi

I'll tidy up the code and release it. I'm happy for anyone to make use of it if they can

MikeD

_________________
Work In Progress:
Atic Atac Remake
MegaBlast (First Slick Game I started)

Top

 Post subject: Posted: Fri Sep 12, 2008 4:27 pm
 Regular

Joined: Sun Feb 24, 2008 6:31 pm
Posts: 163
Location: UK
I've not had time to tidy the code up at all, so it is what it is. If you can use it then feel free.

Code:
package com.daleyuk.raycaster;

import org.newdawn.slick.AppGameContainer;
import org.newdawn.slick.BasicGame;
import org.newdawn.slick.Color;
import org.newdawn.slick.GameContainer;
import org.newdawn.slick.Graphics;
import org.newdawn.slick.Image;
import org.newdawn.slick.Input;
import org.newdawn.slick.SlickException;

public class RayCaster extends BasicGame {

private static final int mapWidth = 24;
private static final int mapHeight = 24;
private int[][] worldMap = new int[][] {
{4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,7,7,7,7,7,7,7,7},
{4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,7},
{4,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7},
{4,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7},
{4,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,7},
{4,0,4,0,0,0,0,5,5,5,5,5,5,5,5,5,7,7,0,7,7,7,7,7},
{4,0,5,0,0,0,0,5,0,5,0,5,0,5,0,5,7,0,0,0,7,7,7,1},
{4,0,6,0,0,0,0,5,0,0,0,0,0,0,0,5,7,0,0,0,0,0,0,8},
{4,0,7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,7,7,1},
{4,0,8,0,0,0,0,5,0,0,0,0,0,0,0,5,7,0,0,0,0,0,0,8},
{4,0,0,0,0,0,0,5,0,0,0,0,0,0,0,5,7,0,0,0,7,7,7,1},
{4,0,0,0,0,0,0,5,5,5,5,0,5,5,5,5,7,7,7,7,7,7,7,1},
{6,6,6,6,6,6,6,6,6,6,6,0,6,6,6,6,6,6,6,6,6,6,6,6},
{8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4},
{6,6,6,6,6,6,0,6,6,6,6,0,6,6,6,6,6,6,6,6,6,6,6,6},
{4,4,4,4,4,4,0,4,4,4,6,0,6,2,2,2,2,2,2,2,3,3,3,3},
{4,0,0,0,0,0,0,0,0,4,6,0,6,2,0,0,0,0,0,2,0,0,0,2},
{4,0,0,0,0,0,0,0,0,0,0,0,6,2,0,0,5,0,0,2,0,0,0,2},
{4,0,0,0,0,0,0,0,0,4,6,0,6,2,0,0,0,0,0,2,2,0,2,2},
{4,0,6,0,6,0,0,0,0,4,6,0,0,0,0,0,5,0,0,0,0,0,0,2},
{4,0,0,5,0,0,0,0,0,4,6,0,6,2,0,0,0,0,0,2,2,0,2,2},
{4,0,6,0,6,0,0,0,0,4,6,0,6,2,0,0,5,0,0,2,0,0,0,2},
{4,0,0,0,0,0,0,0,0,4,6,0,6,2,0,0,0,0,0,2,0,0,0,2},
{4,4,4,4,4,4,4,4,4,4,1,1,1,2,2,2,2,2,2,3,3,3,3,3}
};
//   private int[][] worldMap = new int[][] {
//         { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
//         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 0, 0, 0, 0, 3, 0, 3, 0, 3, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 2, 0, 3, 0, 2, 0, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 2, 2, 0, 2, 2, 0, 0, 0, 0, 3, 0, 3, 0, 3, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 4, 0, 4, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 4, 0, 0, 0, 0, 5, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 4, 0, 4, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 4, 0, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
//         { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };

private double posX;
private double posY;
private double dirX;
private double dirY;
private float planeX;
private float planeY;
int side; // Was a NS or EW wall hit?

private final static int texWidth = 64;
private final static int texHeight = 64;
private Image texture;
private Image newTexture;

/*
*
* @see org.newdawn.slick.BasicGame#init(org.newdawn.slick.GameContainer)
*/
@Override
public void init(GameContainer container) throws SlickException {

posX = 22;
posY = 12;
dirX = -1;
dirY = 0;
planeX = 0;
planeY = 0.66f;
texture = new Image("res/icon.png");
newTexture = new Image(1, 64);
}

/*
*
* @see org.newdawn.slick.BasicGame#update(org.newdawn.slick.GameContainer,
* int)
*/
@Override
public void update(GameContainer container, int delta)
throws SlickException {

double moveSpeed = 18 * 0.004f;
double rotSpeed = 18 * 0.003f;

// move forward if no wall in front of you
if (container.getInput().isKeyDown(Input.KEY_UP)) {
if (worldMap[(int) (posX + dirX * moveSpeed)][(int) posY] == 0)
posX += dirX * moveSpeed;
if (worldMap[(int) posX][(int) (posY + dirY * moveSpeed)] == 0)
posY += dirY * moveSpeed;
}

// move backwards if no wall behind you
if (container.getInput().isKeyDown(Input.KEY_DOWN)) {
if (worldMap[(int) (posX - dirX * moveSpeed)][(int) posY] == 0)
posX -= dirX * moveSpeed;
if (worldMap[(int) posX][(int) (posY - dirY * moveSpeed)] == 0)
posY -= dirY * moveSpeed;
}

// rotate to the right
if (container.getInput().isKeyDown(Input.KEY_RIGHT)) {
// both camera direction and camera plane must be rotated
double oldDirX = dirX;
dirX = dirX * Math.cos(-rotSpeed) - dirY * Math.sin(-rotSpeed);
dirY = oldDirX * Math.sin(-rotSpeed) + dirY * Math.cos(-rotSpeed);
double oldPlaneX = planeX;
planeX = (float) (planeX * Math.cos(-rotSpeed) - planeY * Math.sin(-rotSpeed));
planeY = (float) (oldPlaneX * Math.sin(-rotSpeed) + planeY * Math.cos(-rotSpeed));
}

// rotate to the left
if (container.getInput().isKeyDown(Input.KEY_LEFT)) {
// both camera direction and camera plane must be rotated
double oldDirX = dirX;
dirX = dirX * Math.cos(rotSpeed) - dirY * Math.sin(rotSpeed);
dirY = oldDirX * Math.sin(rotSpeed) + dirY * Math.cos(rotSpeed);
double oldPlaneX = planeX;
planeX = (float) (planeX * Math.cos(rotSpeed) - planeY * Math.sin(rotSpeed));
planeY = (float) (oldPlaneX * Math.sin(rotSpeed) + planeY * Math.cos(rotSpeed));
}

}

/*
*
* @see org.newdawn.slick.Game#render(org.newdawn.slick.GameContainer,
* org.newdawn.slick.Graphics)
*/
public void render(GameContainer container, Graphics g)
throws SlickException {

double w = container.getWidth();
double h = container.getHeight();

for (int x = 0; x < w; x++) {

/* Calculate the ray position and direction */
double cameraX = 2 * x / w - 1; // x-coordinate in camera space
double rayPosX = posX;
double rayPosY = posY;
double rayDirX = dirX + planeX * cameraX;
double rayDirY = dirY + planeY * cameraX;

/* Which box in the map are we in */
int mapX = (int) rayPosX;
int mapY = (int) rayPosY;

/* Length of ray from current position to next x or y-side */
double sideDistX;
double sideDistY;

/* Length of ray from one x or y-side to next x or y-side */
double deltaDistX = Math.sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX));
double deltaDistY = Math.sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY));
double perpWallDist;

/* What direction to step in x or y-direction (either +1 or -1) */
int stepX;
int stepY;

int hit = 0; // Was a wall hit?

/* Calculate step and initial sideDist */
if (rayDirX < 0) {
stepX = -1;
sideDistX = (rayPosX - mapX) * deltaDistX;
} else {
stepX = 1;
sideDistX = (mapX + 1.0 - rayPosX) * deltaDistX;
}

if (rayDirY < 0) {
stepY = -1;
sideDistY = (rayPosY - mapY) * deltaDistY;
} else {
stepY = 1;
sideDistY = (mapY + 1.0 - rayPosY) * deltaDistY;
}

/* Perform DDA */
while (hit == 0) {
/* jump to next map square, OR in x-direction, OR in y-direction */
if (sideDistX < sideDistY) {
mapX += stepX;
side = 0;
} else {
mapY += stepY;
side = 1;
}

// Check if the ray has hit a wall
if (worldMap[mapX][mapY] > 0)
hit = 1;
}

// Calculate distance projected on camera direction (oblique
// distance will give fisheye effect!)
if (side == 0) {
perpWallDist = (float) Math.abs((mapX - rayPosX + (1 - stepX) / 2) / rayDirX);
} else {
perpWallDist = (float) Math.abs((mapY - rayPosY + (1 - stepY) / 2) / rayDirY);
}

// Calculate height of the line to draw on screen
int lineHeight = (int) (Math.abs(h / perpWallDist));

// calculate lowest and highest pixel to fill in current stripe
int drawStart = (int) (-lineHeight / 2 + h / 2);
if (drawStart < 0)
drawStart = 0;
int drawEnd = (int) (lineHeight / 2 + h / 2);
if (drawEnd >= h)
drawEnd = (int) (h - 1);

//         int texNum = worldMap[mapX][mapY] -1;
//
//         /* Calculate value of wallX */
//         double wallX; //Where exactly the wall was hit
//         if (side == 1) {
//            wallX = rayPosX + ((mapY - rayPosY + (1 - stepY) / 2) / rayDirY) * rayDirX;
//         } else {
//            wallX = rayPosX + ((mapX - rayPosX + (1 + stepX) / 2) / rayDirX) * rayDirY;
//         }
//
//         wallX -= (float) wallX;
//
//         /* x-coordinate on the texture */
//         int texX = (int) (wallX * (double) texWidth);
//         if (side == 0 && rayDirX > 0) texX = texWidth - texX - 1;
//         if (side == 1 && rayDirY < 0) texX = texWidth - texX - 1;
//
//         for (int y = drawStart; y < drawEnd; y++) {
//            int d = (int) (y * 256 - h * 128 + lineHeight * 128);
//            int texY = ((d * texHeight) / lineHeight) / 256;
////            Color c = texture.getColor(texX, texY);
////            g.setColor(c);
////            g.drawLine(x, y, x, y);
//         }

// choose wall color
Color color;
switch (worldMap[mapX][mapY]) {
case 1:
color = Color.red;
break; // red
case 2:
color = Color.green;
break; // green
case 3:
color = Color.blue;
break; // blue
case 4:
color = Color.white;
break; // white
default:
color = Color.yellow;
break; // yellow
}

// give x and y sides different brightness
if (side == 1) {color = color.darker(0.5f);}

// draw the pixels of the stripe as a vertical line
// verLine(x, drawStart, drawEnd, color);
g.setColor(color);
g.drawLine(x, drawStart, x, drawEnd);
//System.out.println(posX + ":" + posY);
}

}

public RayCaster(String title) {
super(title);
}

/**
* @param args
*/
public static void main(String[] args) {
try {
AppGameContainer container = new AppGameContainer(new RayCaster(
"RayCaster"));
container.setDisplayMode(800, 600, false);
container.setTargetFrameRate(60);
container.setVSync(true);
container.start();
} catch (SlickException e) {
e.printStackTrace();
}
}

}

MikeD

_________________
Work In Progress:
Atic Atac Remake
MegaBlast (First Slick Game I started)

Top

 Post subject: Posted: Wed Sep 17, 2008 10:27 am

Joined: Fri Oct 05, 2007 9:00 pm
Posts: 51
Location: japan
@miked

thanks a lot for the code!
i'll try to understand it, anyway nice

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 10 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: No registered users and 2 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ General    Games / Demos    Help / Discussion    Community Projects    Game Ideas/Design    Slick Competition 2011    Android Slick - LWJGL 2D Game Library    Announcements    Bug Reports / RFE    Extensions    Contribution depot Related Libraries and Tools    Phys2D    Tiled    TWL    Fizzy    Artemis Archive    Resolved Bugs/RFE    Useful Posts