Raycasting on J2ME device?

[daybyter]

Hi!

I was looking over some sites with Java raycasting  engines (like http://www.geocities.com/siliconvalley/campus/5009/javamazedemo.html ), and was wondering, if it's currently feasable to port some of them to J2ME. What do you think?

Ciao,
Andreas

[jbanes]

Definitely not MIDP 1.0. 1.0 gives you no way to scale image data or deal with pixel buffers. MIDP 2.0 might work, but I don't know enough about what it contains.

[Abuse]

it'd be possible in midp1.0 if you relied on the nokia extensions, and is definitly possible in midp2.0.

However, you will have problems with speed.

The GBA struggles with Doom (and thats a dedicated games machine, running native code...),
so im not sure it'll be within the capabilities of current phones. (even the very latest of them)

Games published by our own members! Check 'em out!

[shareme]

it'd be possible in midp1.0 if you relied on the nokia extensions, and is definitly possible in midp2.0.

However, you will have problems with speed.

The GBA struggles with Doom (and thats a dedicated games machine, running native code...),
so im not sure it'll be within the capabilities of current phones. (even the very latest of them)

Yes but that is with fully textured games..what if you creatively elimnated the need for fully textured objects?

[daybyter]

I'd start with the most simple approach. Compute the length of the wall, then paint the wall in one color, roof and bottom in another color. That's almost castle Wolfenstein?

[shareme]

I'd start with the most simple approach. Compute the length of the wall, then paint the wall in one color, roof and bottom in another color. That's almost castle Wolfenstein?

the game StrangeMaze on J2ME uses a raycaster

If you check my weblog for the day of yesterday I have a link to resources that describe Wolfensteins engine

http://www.freeroller.net/page/shareme/Weblog

[daybyter]

This StrangeMaze game seems to be a pretty good start. I guess that's the direction J2ME games will go in the future...

On the Wolfenstein link: you mean the phoenixgarage.org link? I could only find a link to some Doom details there...

[shareme]

This StrangeMaze game seems to be a pretty good start. I guess that's the direction J2ME games will go in the future...

On the Wolfenstein link: you mean the phoenixgarage.org link? I could only find a link to some Doom details there...

Ddi you see the c implmentation link with actual code?

Goging through all the notes there you can then make decisions based upon what Java target you have either J2ME or J2se..

[daybyter]

Did not see the C implementation. But  I guess the initial implementation is pretty much obvious. The question is just, if a J2ME device can run bresenham 100x and still achieve a reasonable framerate. But it seems that StrangeMaze is already the answer to this question...

[shareme]

Did not see the C implementation. But  I guess the initial implementation is pretty much obvious. The question is just, if a J2ME device can run bresenham 100x and still achieve a reasonable framerate. But it seems that StrangeMaze is already the answer to this question...

There are tricks to reducing frame rate as well..

remeber your takign all that info on the link and looking for how you can optmize both math calculations, memory space, and etc so if you look to view the info with that in mind you can start to see where specific choices can be made..that make it possible on J2ME..

Games published by our own members! Check 'em out!

[jbanes]

if a J2ME device can run bresenham 100x and still achieve a reasonable framerate.

Just out of curiousity, what would you need bresenham's algo for in a raycaster? The floor and ceiling are simply filled backgrounds (half the screen to the ceiling, half the screen to the floor) broken by the walls that are drawn. Since the walls are drawn in vertical "slivers" (a straight line of texture or color) no fancy calculations are needed. Is there something I'm missing here?

[daybyter]

if a J2ME device can run bresenham 100x and still achieve a reasonable framerate.

Just out of curiousity, what would you need bresenham's algo for in a raycaster? The floor and ceiling are simply filled backgrounds (half the screen to the ceiling, half the screen to the floor) broken by the walls that are drawn. Since the walls are drawn in vertical "slivers" (a straight line of texture or color) no fancy calculations are needed. Is there something I'm missing here?

How do you compute what wall you are looking at and how far away from the player it is?
If look at the 1st diagram here
http://www.phoenixgarage.org/homevr/resources/renderingsoftware/25d/wolf3dstyle/doom.txt
, you see the problem.
How to compute each ray? My first, maybe rather naive, approach would be to run Bresenham's line algo for each column of the screen. Maybe compute fixed offsets for each line (representing a view angle), and then simply add those offsets to the player's current position. Run the line algo to find the first collision with any object (maybe support by some quadtree data structure for any objects in the scene) . If no objects are hit by the ray, paint some black background or simply leave roof and ground as they are (they could fade out to black towards the middle of the screen).

[tom]

How do you compute what wall you are looking at and how far away from the player it is?

You could use a bsp tree.

[jbanes]

> How do you compute what wall you are looking at and how
> far away from the player it is?

Ah. I see the problem. Bresenham would most likely be too slow and BSP would be too memory intensive. I was going to try to explain the math here, but it would just take too much time for me to write. After all, it's an algo with a lot of gotchas. I highly recommend finding a used copy of "Tricks of the Game Programming Gurus". It's the best source I know of for Ray Casting. Here's a high level description:

You need to remember that your walls need to actually be square "blocks" that take up a square number of world coordinates (i.e. 64x64). You test only every block and not for every coordinate. This speeds things up tremendously.

Use the slope of each ray to calculate the next intersection. Depending on the angle of the ray, it may intersect both vertical and horizontal walls. You'll need to check each wall for both vertical and horizontal for each block the ray passes through until the ray goes past the clipping range or intersects with a wall. The formulas are something like this:

Let w = next wall from player or previous intersection
Let p = player location

Since the player is "inside" an empty block, you need to test for the first intersection. Here's the formulas:

yIntersection = raySlope * (xw - xp) + yp
xIntersection = (raySlope exp -1) *(yi - yp) +xp

Every intersection after that uses the formulas:

nextYIntersection = previousYIntersection + raySlope * blockHeight
nextXIntersection = previousXIntersection + (raySlope exp -1) * blockWidth

Once you find a wall, you should have coordinates for both the player and the intersection. Use these coordinates as values to calculate the hypotenuse of a right triange (Pythagorean theorem). There are ways of optimizing this that I'm not going to get into right now. The hypotenuese is the distance of the player from the "sliver". You can use this to calculate how tall the sliver should be. A simple inverse (1/distance) calc should work fine on a square pixel screen. If you have a non-square screen (i.e. 320x200) try using a different value than 1 to adjust for distortion (i.e. 1.5/distance).

Last problem. This method mixes polar (circular) coordinates with cartesian (rectangular) coordinates. this causes spherical distortion. (Like looking through a fish bowl). Getting rid of it is a bit more math. You multiply the scale of the sliver against the (cos exp -1) of the current ray. Just to be clear, this is the cosine of your field of view (i.e. -30 to +30 degrees) and not the actual direction (i.e.  300 to 360 degrees) the player is looking.

I don't know how helpful this is as Raycasting is a very involved topic. Never the less, there you are. My only suggestion is that you first try making this work using a normal Java application, then later port the code to MIDP. That way you can work out the bugs in what you're doing.

[jbanes]

Just to add:

Slope calculation:
http://syllabus.syr.edu/cid/graph/Unit4a.html

Very pretty, but low on details, Raycasting tutorial:
http://www.permadi.com/tutorial/raycast/

Another Raycasting tut:
http://tigcc.ticalc.org/tut/raycasting.html

[daybyter]

I watched the review of Elkware's internal gate on TV yesterday
http://www.midlet-review.com/images_color/infernalgate.gif
, and it looks really good. So raycasting is feasable on a cellphone. Asked the developers what methods they use and they told me it's MIDP 1 plus a Nokia method to draw a screenbuffer. Texture scaling seems to be done with MIDP 1 only.

[BinaryChester]

I may be totally wrong, but i think "infernal gate" is an Series 60 app, so it is done in c++ and not Java?


Gtx, Heiko