Slick Forums

Discuss the Slick 2D Library
It is currently Wed Aug 21, 2019 9:02 am

All times are UTC




Post new topic Reply to topic  [ 10 posts ] 
Author Message
PostPosted: Sun Aug 10, 2008 5:00 am 
Offline
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.

Anyway, here's the link: http://anotherearlymorning.com/blog/physical-queries-for-the-math-challenged


Top
 Profile  
 
 Post subject:
PostPosted: Sun Aug 31, 2008 3:09 am 
Offline
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.

Please leave comments ot let me know what you think!

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


Top
 Profile  
 
 Post subject:
PostPosted: Mon Sep 01, 2008 9:41 am 
Offline
Regular
User avatar

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
 Profile  
 
 Post subject:
PostPosted: Mon Sep 01, 2008 1:33 pm 
Offline

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
 Profile  
 
 Post subject:
PostPosted: Mon Sep 01, 2008 3:59 pm 
Offline
Regular
User avatar

Joined: Sun Feb 24, 2008 6:31 pm
Posts: 163
Location: UK
:D 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 :D

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
 Profile  
 
 Post subject:
PostPosted: Mon Sep 01, 2008 4:57 pm 
Offline
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
 Profile  
 
 Post subject:
PostPosted: Fri Sep 12, 2008 9:31 am 
Offline

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
 Profile  
 
 Post subject:
PostPosted: Fri Sep 12, 2008 9:40 am 
Offline
Regular
User avatar

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 :D

MikeD

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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Sep 12, 2008 4:27 pm 
Offline
Regular
User avatar

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;

   /*
    * (non-Javadoc)
    *
    * @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);
   }

   /*
    * (non-Javadoc)
    *
    * @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));
      }

   }

   /*
    * (non-Javadoc)
    *
    * @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) {
               sideDistX += deltaDistX;
               mapX += stepX;
               side = 0;
            } else {
               sideDistY += deltaDistY;
               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
 Profile  
 
 Post subject:
PostPosted: Wed Sep 17, 2008 10:27 am 
Offline

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
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 33 guests


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

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group