This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.
Topics - ZippyDee
1
« on: September 27, 2017, 06:08:27 pm »
Before reading, check out this wonderful old flash game from which I blatantly stole this concept: http://www.ferryhalim.com/orisinal/g2/dozen.htm (Also that site has some ridiculously adorable stuff. Check it all out. But first read my post and help me ok good thanks cool.) The concept of the game is simple: you're in a basket, you have to jump straight up to land in the next basket. Jumps are always perfectly vertical an always the same height. In that game, the layout is all predefined and it has an end. I started thinking about how one might randomly generate the next basket to jump to in real time in order to make an infinitely scrolling game. This seemed simple at first, and certainly could be simple with an assortment of predefined cookie-cutter paths for the baskets to follow that could be used, but that doesn't make things interesting. When considering generating arbitrary paths or paths arbitrarily modified from a set of "template" path shapes (rather than exact predefined paths) with varying basket speeds and basket starting positions, the problem becomes a lot more complicated. The first goal is to be able to determine whether a given pair of baskets makes a valid level, and then to assign the level a "difficulty" score. To do this we determine the periods of the two basket paths given path length and basket speed. Then we search through time from 0 to the LCM of the two periods, looking at the X and Y of the paths in order to locate all contiguous ranges ("windows") of t values at which jumping would land you in the upper basket. Given the set of jumping windows, difficulty can be derived with a function of number of windows total, size of windows, and time between windows. The actual difficulty scoring function isn't important here, but that's easy enough to create once we have the window data. Let's consider a simplified case using only one positional dimension, y. Imagine a stationary basket on path y=1 directly below a basket moving up and down along path y = sin(2t) + maxJumpHeight. Half the time, the basket will be within jumping range (when yupper < ylower + maxJumpHeight) and the other half it will be too high. The LCM of the period of the paths is ~3.14 timesteps (seconds? sure), considering stationary paths as having a period of 1 not 0. Now for every time t in range [0,3.14] we can plot the y values of the two baskets at t. Now let's say it takes ~0.7s for the ball to reach a maxJumpHeight of 2 or so. Now we can easily plot the peak jump height for a jump starting at any given t value. This can be plotted as y = ylower(t-0.7) + 2 Plotting those should look something like this:  Blue = upper path over time Orange = lower path over time (slanted for visibility because colors are dumb) Red = ball max height over time (slanted to show how offset lines up) Any point at time ton the red line actually represents the peak of a jump if you had jumped at time t-0.7. As long as we know this, we can ignore that offset as we only care about the ball's path and the upper basket's path at time t. This implies that there are 2 places where you can land in the upper basket: intersections at points A and B. But that assumes you can ONLY land at the peak of your jump. We actually need to add another dimension to this because we care about all points along the ball's falling trajectory, not just the peak. To add this additional dimension, we must consider how long the ball has been falling for: a jump offset axis j. This axis projects the falling motion forward in time for each second of j since the peak of a jump. Projecting this through the sine wave path of y uper extended into the j dimension, we can see that there are many collisions along the falling path. Because we care only about points after the jump peak, instead of projecting the jump paths forward in time for each timestep of j, I decided to project the falling arcs straight out along the j axis and project the basket path backwards for each timestep of j. These should be equivalent transformations. By projecting the falling arcs straight along the j axis, I know this is confusing as heck. I've tried to make these graphs as clear as possible but it's hard with what I'm using... X axis = t; Y axis = y; Z axis = j    (I messed that graph up 3 times before even posting this, so I hope this time it's right) Note that the sine wave position projects backward through X (t) for each Z (j) timestep, and the parabolic arcs project straight in the Z (j) plane. This should be equivalent to the sine wave projecting straight out in the Z axis and the jump arcs projecting forward through X for each Z step, right? I think that's right.Hopefully you can tell that at SOME point along the right hand side of the graph there is an intersection between the half parabola of the falling arc and the position vector of the upper basket. Any intersection implies that jumping at time t-0.7 would land you in the basket at time t. THEREFORE, a valid value of t is one at which there is an intersection at any j value after the peak of the jump. In this graph, the "jump window" would be the second half of the interval. You could jump any time during that window and you would still land in the basket. Ok, now that we've done it with a 1D position axis, add another one. Instead of only considering the Y value, we need to consider X and Y for the jump arcs and the basket paths at each time and jump offset. This makes the resulting graph 4-dimensional, meaning 3D intersections at any given t value rather than 2D.....yay.... I feel like I simply can't wrap my head around how to do any calculation for this (even in the simplified case) to effectively locate t values that contain intersections without just iterating over each one and running a 2D/3D intersection on the functions using j as the sole independent. Is there some sort of magic I could be using here? --- I should also mention that this doesn't even begin to cover GENERATING the next path, just locating the jump windows for a given pair of paths...It's possible that it could be easier to generate a path that is guaranteed valid rather than validating an existing path, though I'm not sure how to figure that out either. Thanks for taking the time to read all this. If there's any way I can clarify things, please ask. I think I have all the pieces in my brain to set up the situation, I just don't have the math to solve it, so hopefully I can explain any questions you might have. -Taw
2
« on: December 02, 2013, 04:47:39 pm »
After many months, Hello! I am back with a question! I have written an implementation of a Breadth First Search algorithm that doesn't use queues or stacks to search for the goal node, and instead uses fixed buffers! I have the search written, and now I'm writing the backtracking part of it to find a path from the goal back to the start node. THE ALGORITHM:The implementation uses three bit-mapped 128 byte buffers to represent a 32x32 map. These buffers are contiguous in RAM. (listed in order) b_tilemap: each bit represents whether a tile is walkable or not. 0 = empty, 1 = wall. b_closed: each bit represents whether this node has been visited or not by the search algorithm b_nodes: each bit represents the value assigned to the node when it was visited. This value is used for backtracking, and this is why the algorithm is interesting! When the routine starts, the bit of the starting node in b_closed is set. Each iteration of the search passes over the entire buffer. Every bit in the b_closed buffer is "expanded" into each of the 4 adjacent bits that are not walls in b_tilemap. Any newly expanded bits that were not already set in the b_closed buffer are assigned a value of either 1 or 0 in the b_nodes buffer. This value is the same for every new bit expanded during the iteration. After each pass, the bit of the goal node is tested in b_closed. If it is set, we know the goal node has been visited, so we can now backtrack from here to the start by following our b_nodes values! The assigned b_nodes value follows the pattern 0, 1, 1, 0, 0, 1, 1, 0, etc, changing each iteration to the next value in the pattern. This is the key to this algorithm. At any given index in this pattern, the previous and next indices always have different values. With a reference of the current value and either the next value or the previous value in the pattern, the third value can always be determined. You can walk a path by walking to adjacent nodes that match the next value in the pattern. Obviously from the starting node every possible route follows this pattern, because it all expanded from that point. However, if we follow the pattern in the reverse direction from where we ended, it will always lead us from the goal back to the start. There may be multiple paths, but, if so, all paths will be the same length, so it doesn't matter which path is taken. The backtracked path is the only part of this algorithm that uses variable memory, because we obviously can't know how long the path is until we've found it! I HOPE THAT ALL MAKES SENSE...  If not, I would love to clarify. //EDIT: PICTURES! Here you can see that it expands every possible node each pass. The value assigned follows the pattern I described. Once the goal is found, you can follow the pattern in reverse to find your way back. That was the path I chose to follow, but any of these paths would be valid, because they all follow the pattern:       Note that they are all the exact same length. So technically the set of valid tiles to move to is:  THE PROBLEM:This algorithm is designed to do a search in 4 directions only, however I realized that backtracking correctly can produce an 8-directional path, which I would greatly prefer. Note that any time it has multiple possible paths, all options will produce the same length of 4-directional path, so any time you can move diagonally is ALWAYS an improvement. The algorithm should always try to move in a straight line, unless it has the option to move diagonally (and is not moving diagonally in a different direction already, of course). This creates the most efficient paths with 8-directional movement and accounts for the possibility that changing direction has a cost (such as enemies having to turn to face a new direction before moving that way). The way I thought of to implement diagonal movement is to compare the "options" from the previous node in the path with the "options of the current one. For example, let's say at node A you can move either right or down, so you choose to move right and add that node to the backtracked path. Now at node B you can move either right, down, or up. Well if you compare with the valid directions at A, you can see that down was valid for node A, too! That means the node diagonally down-right from A is valid and not blocked by any walls or corners! So instead of adding a new node to the backtracked path, we just change the last node we added to be right-down from A, instead of just right. //EDIT: The returned path can be quite small if represented by a series of directions 0-7. The layout I have for this is 0=right, going counter-clockwise around the directions (1=up-right, 2=up, 3=up-left, etc). It's easy to expand any format of directions like that into an X and Y offset using a couple of LUTs.Does that make sense as well? I hope so, because the question is... How do you do that efficiently? All of it. What's the most efficient way to check the 4-directional surrounding bits recursively like that? Am I missing a more efficient way to check diagonal pathing? I just can't come up with a way to write this backtracking that I feel is very efficient. Thanks so much for any input! I'll clarify anything that is confusing if need be! -Taw
3
« on: May 03, 2012, 08:01:19 pm »
I've been thinking about this all day and I can't figure it out...
Say you have three known points p0, p1, and p2. Each of these points serves as the focus of a parabola, and all three parabolas share a single line at y=d as their directrix. Assume that d is such that all three parabolas open in the same direction, and assume that the three foci do NOT all lie on a single line parallel to the directrix.
So the idea is to solve for value of d that makes all three parabolas intersect at a single point. There should only be one value that makes this true.
Basically, so far I've got quite a bit conceptually figured out in terms of what needs to happen...but I don't really know how to make it happen.
Here's kinda what I have:
The intersection point(s) of two parabolas (zn)can be calculated fairly easily:
z0=a0x2+b0x+c0
z1=a1x2+b1x+c1
Find the quadratic equation that is the difference of the two, and set it equal to zero:
0=(a0-a1)x2+(b0-b1)x+(c0-c1)
Use the quadratic formula to find the zeros:
x=(-(b0-b1)±√((b0-b1)2-4(a0-a1)(c0-c1)))/2(a0-a1)
A parabola can also be written as (x-h)2=4p(y-k), where (h,k) is the vertex of the parabola, (h,k+p) is the focus, and the directrix lies at y=k-p
With a focal point F and a directrix at y=d, all other necessary variables can be calculated as follows:
p=(Fy-d)/2
h=Fx
k=Fy-p
a=1/4p
b=-h/2p
c=h2/4p+k
Through this, all variables can be simplified down to only use F and d:
a=1/2(Fy-d)
b=-Fx/(Fy-d)
c=Fx2/2(Fy-d)+Fy-(Fy-d)/2[/tt]
So you could technically write out the equation of a parabola as
y = x2/2(Fy-d) + -Fxx/(Fy-d) + Fx2/2(Fy-d)+Fy-(Fy-d)/2
As you can see, it gets pretty hectic pretty quickly. For example, the quadratic formula would then be:
x=(Fx/(Fy-d)±√((-Fx/(Fy-d))2-(2/(Fy-d))(Fx2/2(Fy-d)+Fy-(Fy-d)/2)))/(1/(Fy-d))
Remember, this needs to be solving for d...
Really, I don't know where to go from here. Anyone have any insight?
---EDIT:
Okay, so I'm slowly figuring things out.
The equation is crazy complex, but you have to solve for the intercepts of two parabolas, then plug that quadratic formula calculation in for X in one of those equations, and set it equal to the equation for the third parabola with the quadratic formula calculation plugged in for X as well.
a2((-(b0-b1)±√((b0-b1)2-4(a0-a1)(c0-c1)))/2(a0-a1))2+b2((-(b0-b1)±√((b0-b1)2-4(a0-a1)(c0-c1)))/2(a0-a1))+c2=a0((-(b0-b1)±√((b0-b1)2-4(a0-a1)(c0-c1)))/2(a0-a1))2+b0((-(b0-b1)±√((b0-b1)2-4(a0-a1)(c0-c1)))/2(a0-a1))+c0
Looks like fun, right? Now substitute the As, Bs, and Cs with their F/d equivalents that I mentioned earlier, accounting for the fact that the Fs have to be Fnx and Fny for each variable of the corresponding n value.
4
« on: February 27, 2012, 04:02:50 pm »
This has been in the works for a few weeks now, so I thought I'd make a thread about it. I began writing this Axiom with a fixed-memory flood fill routine, but I failed miserably. I finally convinced jacobly to give it a try. Together we completely optimized the algorithm and he was able to write an awesomely optimized version. Then I started working on a filled circle algorithm, which jacobly volunteered to convert to Axiom format for me, but a few *cough* bugs were found. He has since been working with me to fix those bugs. All-in-all, this is basically an Axiom by both jacobly and myself. This Axiom will be a collection of more advanced graphics routines which we hope will be greatly useful for graphics programs, and potentially games as well. Some of the routines will definitely NOT be useful for games, due to speed issues. Currently written: - Fixed-Memory Flood Fill (needs optimization)
"Fixed-memory" means there is no risk for stack overflow AT ALL. However, the routine is subsequently very slow, so it will not be suitable for games or anything that needs fast dynamic area filling. It would be fine for a "paint bucket" tool in most on-calc graphics programs though. This will *hopefully* support grayscale filling as well.- Filled Circles (aaalmost done)
Fully clipped filled circle routine with variable buffer and variable fill type (on/off/invert) using numerical arguments.Kinda sorta planned: - Vertical/Horizontal Line Segments (on/off/invert)
- Clipped Lines (on/off/invert)
- Rectangles (on/off/invert)
- Rectangle outlines (on/off/invert)
- Ellipses?
Any other suggestions for what this axiom could have?
5
« on: February 10, 2012, 02:56:04 am »
So, I was trying to write an assembly program to execute a fixed-memory flood fill routine as described by the "flood fill" Wikipedia article here, but I realized that the algorithm written there is poorly explained, and also missing a lot of crucial conditions. After realizing this, I opened up Adobe Flash to try to write an implementation so that I could easily see what was going on at all times, and could therefore debug it a lot more easily. After hours of debugging and modifications, I finally was able to write an algorithm that actually worked in all situations. Here is the pseudocode I have written out for it: RULE is "right"
FINDLOOP is false
BOTTLENECK is false
CUR is the current pixel
MARK is the first mark, and is not set
MARK2 is the second mark, and is not set
main loop:
if CUR is bound by 4 edge pixels
paint CUR
all possible pixels have been filled, so exit the routine
if CUR is bound by 3 edge pixels
paint CUR
move based on RULE
continue main loop
if CUR is bound by 2 edge pixels
if the two bounding edge pixels are not across from each other, and the corner opposite both edge pixels is not filled
paint CUR
move according to RULE
continue main loop
else
if RULE is "right" and MARK is not set
set MARK to CUR's location and direction
set FINDLOOP to false
else, if MARK is set
if MARK2 is not set
if CUR is at MARK's location
if CUR's direction is the same as MARK's
remove MARK
set RULE to "right"
else
set RULE to "left"
set CUR to MARK's direction
set FINDLOOP to false
else, if FINDLOOP is true
set MARK2 to CUR's location and direction
else
if CUR is at MARK's location
set CUR to MARK2's direction and location
remove MARK
remove MARK2
set RULE to "right"
else if CUR is at MARK2's location
set MARK to MARK2's direction and location
set CUR's direction to MARK2's direction
remove MARK2
if RULE is "right" and MARK is not set
if BOTTLENECK is false
paint CUR
set BOTTLENECK to false
move according to RULE
continue main loop
if CUR is bound by 1 edge pixel
if RULE is "left" and FINDLOOP is false
set FINDLOOP to true
else, if neither of the corners opposite the bounding pixel are filled
paint CUR
move according to RULE
continue main loop
if CUR is bound by 0 edge pixels
if RULE is "left" and FINDLOOP is false
set FINDLOOP to true
set BOTTLENECK to false
move any direction (use a default direction, not a random one)
continue main loop
##############################
how to move according to RULE:
if CUR is filled or the rule-side-corner is filled
move CUR one step forward
else
if MARK is at the pixel one step forward
set BOTTLENECK to true
else, if MARK2 is at the pixel one step forward
set MARK to MARK2's direction and location
set CUR's direction to MARK2's direction
remove MARK2
if RULE is "left" and FINDLOOP is false
if either the pixel two steps forward is filled or the non-rule-side pixel is filled
set FINDLOOP to true
move CUR one step forward
move CUR one step to the RULE side
##############################
every time you paint:
remove MARK, if set
remove MARK2, if set
set FINDLOOP to false
set BOTTLENECK to false
set RULE to "right"I'd like to put this into the Wikipedia article so that people can have a much better example to base their code on. Is there any way I should modify this pseudocode to make it look better? I am also going to create some images explaining what some things are (like what an "open corner" is, as opposed to a "closed corner"). Also, if someone wants to write an ASM implementation of this, please go ahead. I bet your implementation would be better than mine >.<
6
« on: February 08, 2012, 03:39:36 am »
For a while now I've been thinking about writing a fixed-memory flood fill routine. I finally wrote one out....but it doesn't work. I'm not very good at using the wabbitemu debugger, so debugging this is turning into an incredibly difficult job for me. I was wondering if someone could help me look through this and see if they can't assist me in figuring out what's wrong. I can try to clarify any questions you have in any parts of the routines. Note that this is mostly optimized for speed because of the inevitably slow speed of this flood fill method. EDIT: I attached a screenshot of what it does right now if you just execute it. EDIT2: I made some modifications to the routine, but it's still buggy. The screenshot is not entirely accurate anymore. Now is' basically doing the same thing, only to the right of pxl(10,10) rather than to the left of it... EDIT3: Updated the explanation of how the "right hand rule" should be followed at the bottom of my pseudocode. It should make more sense now... I wrote this routine based off of the fixed memory flood fill routine loosely described here: http://en.wikipedia.org/wiki/Flood_fill#Fixed_memory_method_.28right-hand_fill_method.29I first wrote up this pseudocode: This algorithm:
http://en.wikipedia.org/wiki/Flood_fill#Fixed_memory_method_.28right-hand_fill_method.29
RULE = right
MARK = null
MARKDIR = null
FINDPASSAGE = false
-----
if 4 bounds painted
paint cur
stop
else if 3 bounds painted
MARK = null
FINDPASSAGE = false
RULE = right
paint cur
move to open bound
//#######################
else if 2 bounds painted
if MARK == null && RULE == right
MARK = cur
MARKDIR = dir
FINDPASSAGE = false
else if cur == MARK
if dir == MARKDIR
MARK = null
else
RULE = left //.....this stuff here is the "oh no I'm in a loop" stuff.
dir = MARKDIR
MARK = null
FINDPASSAGE = false
if MARK == null && RULE == right
paint cur
move based on RULE //after moving
//set "dir" to the next direction
//according to RULE (right hand rule or left hand rule)
//######################
else if 1 bound painted
if RULE == left //then we're in a loop, and this triggers the second stage
FINDPASSAGE = true
else
if both opposite corners are open && MARK == null
paint cur
move base on RULE
else if 0 bounds painted
if RULE == left
FINDPASSAGE = true
paint cur?
move anywhere :P
========================================
How do you follow the right hand rule? Which is next?
(Key: _ = empty pixel, # = filled pixel, 0 = current position and direction)
if the corner is filled, just move forward
___
_0_
_##
...becomes...
___
__0
_##
but if the corner is empty, there are two possible ways to move
___
_0_
_#_
first possibility
___
_#0 If the current pixel is painted before moving, move here
_#_
second possibility
___
___ if the pixel is NOT painted before moving, move around the corner to the next edge
_#0 because just going straight would make it now have no borders...
Based on that I wrote my assembly program, which is quite messy, I'm sorry to say... #include "ti83plus.inc"
#define progStart $9D95
.org progStart-2
.db $BB,$6D
;these are all flags used in the "bools" address. I didn't use one of the AsmFlags addresses, because that might be in use by whatever program uses this routine.
bool_color .equ 0 ;unused for now. only fills black.
bool_color2 .equ 1 ;unused for now
bool_rule .equ 2 ;set=right-hand rule,reset=left-hand rule
bool_findpath .equ 3 ;set if
bool_filled .equ 4 ;whether or not the current pixel has been filled. This is set when paintCur is called
bool_mark .equ 5 ;if reset, mark is null. otherwise, mark is in use. Used in the main loop
_init:
ld (save_iy),iy
ld iy,bools
ld hl,(cx)
call getPixel
and (hl)
ret nz ;quit if the current pixel is already filled
_main: ;main program loop.
call safecopy ;safecopy exists for testing purposes only.
res bool_filled,(iy)
ld hl,(cx)
call getEdgePixels
ld (bounds), a
;ld (PlotSScreen),a
call SumNibBits
ld b,a
djnz _not1
_1_bound:
bit bool_rule,(iy)
jr nz,+_
set bool_findpath,(iy)
jr ++_
_:
bit bool_mark,(iy)
jr nz,+_
ld hl,(OppCornMask_LUT)
ld d,0
ld e,(iy+off_cdir)
add hl,de
ld a,(bounds)
and (hl)
jr nz,+_
call paintCur
_:
call MoveByRule
_not1:
djnz _not2
_2_bound:
;if MARK == null && RULE == right
bit bool_mark,(iy)
jr nz,_2elseif
;MARK = cur
ld hl,(cx)
ld (mx),hl
;MARKDIR = dir
ld a,(cdir)
ld (mdir),a
;FINDPASSAGE = false
res bool_findpath,(iy)
set bool_mark,(iy) ;mark is not null
_2elseif:
;else if cur == MARK
ld hl,(cx)
ld a,(mx)
cp l
jr nz,_2if
;if dir == MARKDIR
ld a,(my)
cp h
jr nz,_2if
ld a,(cdir)
ld hl,mdir
cp (hl)
jr nz,_2else
;MARK = null
res bool_mark,(iy)
jr _2if
_2else:
;else
;RULE = left
res bool_rule,(iy)
;dir = MARKDIR
ld a,(hl)
ld (cdir),a
;MARK = null
res bool_mark,(iy)
;FINDPASSAGE = false
res bool_findpath,(iy)
call TurnByRule
_2if:
;if MARK == null && RULE == right
bit bool_mark,(iy)
jr nz,_move
bit bool_rule,(iy)
jr z,_move
;paint cur
call paintCur
;move based on RULE
_move:
call MoveByRule
jp _main
_not2:
djnz _not3
_3_bound:
res bool_mark,(iy)
res bool_findpath,(iy)
set bool_rule,(iy)
call TurnByRule
call paintCur
call MoveByRule
jp _main
_not3:
djnz _not4
_4_bound:
;4 bound
call paintCur
ld iy,(save_iy)
ret ;;QUIT
_not4:
_0_bound:
ld hl,cdir
ld (hl),0
call paintCur
inc hl
inc (hl) ;increase cx
jp _main
bools:
.db 0 | (1 << bool_color) | (1 << bool_color2) | (1 << bool_rule)
cdir: ;current dir. 0=down, 1=left, 2=up, 3=right
.db 0
cx: ;current x. Set to 10 for testing
.db 10
cy: ;current y. Set to 10 for testing
.db 10
mdir: ;mark dir
.db 0
mx: ;mark x
.db 0
my: ;mark y
.db 0
bounds: ;holds the bound data
.db 0 ;bit order: FAHCGDBE
;ABC ;here's how that order lines up with surrounding pixels
;DxE
;FGH
save_iy:
.dw 0
;I reference these using IY+* to load values into other registers. IY points to bools.
;Not all of these are used. In fact, I think only off_cdir is used.
off_cx .equ cx-bools
off_cy .equ cy-bools
off_cdir .equ cdir-bools
off_mx .equ mx-bools
off_my .equ my-bools
off_mdir .equ mdir-bools
off_bounds .equ bounds-bools
;masks for the pixel straight forward, based on dir
.db %00001000, %00000100, %00000010, %00000001
FrontByDirMask_LUT:
; %FAHCGDBE %FAHCGDBE %FAHCGDBE %FAHCGDBE
.db %00001000, %00000100, %00000010, %00000001
.db %00001000, %00000100, %00000010, %00000001
OppCornMask_LUT: ;masks for the two opposite corners from the edges corresponding with FrontByDirMask_LUT
; %FAHCGDBE %FAHCGDBE %FAHCGDBE %FAHCGDBE
.db %01010000, %00110000, %10100000, %1100000
FrontCornRightRuleMask_LUT: ;masks for corners forward/right, based on cdir
; %FAHCGDBE %FAHCGDBE %FAHCGDBE %FAHCGDBE
.db %10000000, %0100000, %00010000, %0010000
FrontCornLeftRuleMask_LUT: ;masks for corners forward/right, based on cdir
; %FAHCGDBE %FAHCGDBE %FAHCGDBE %FAHCGDBE
.db %00100000, %1000000, %01000000, %00010000
.db 1
DirMoveX_LUT: ;LUT for X offsets based on dir. Used in MoveByRule.
.db 0,-1,0
DirMoveY_LUT:
.db 1,0,-1,0
MoveByRule: ;move based on the rule. (this immediately goes into TurnByRule)
bit bool_filled,(iy)
ld e,(iy+off_cdir)
ld d,0
jr z,_moveforward
bit bool_rule,(iy)
ld b,d
ld c,1
ld hl,FrontCornRightRuleMask_LUT
jr z,+_
ld c,-1
ld hl,FrontCornLeftRuleMask_LUT
_:
ld e,(iy+off_cdir)
ld d,b
add hl,de
ld a,(bounds)
and (hl)
jr nz,_moveforward
ld hl,DirMoveX_LUT
add hl,de
add hl,bc
ld a,(cx)
add a,(hl)
ld (cx),a
inc hl
inc hl
inc hl
ld a,(cy)
add a,(hl)
ld (cy),a
_moveforward:
ld hl,DirMoveX_LUT
add hl,de
ld a,(cx)
add a,(hl)
ld (cx),a
inc hl
inc hl
inc hl
ld a,(cy)
add a,(hl)
ld (cy),a
TurnByRule: ;turn based on the rule.
ld hl,FrontByDirMask_LUT
ld d,0
ld e,(iy+off_cdir)
add hl,de
ld e,1
bit bool_rule,(iy)
jr nz,+_
ld e,-1
_:
ld b,(iy+off_bounds)
xor a
ld c,a
_frontloop:
;while front on, rotate opposite from rule
;check front
ld a,b
and (hl)
jr z,_sideloop
dec c
sbc hl,de
jr _frontloop
_sideloopskip:
inc c
_sideloop:
add hl,de
ld a,b
and (hl)
jr z,_sideloopskip
ld a,(cdir)
dec e
jr nz,_leftrotate
add a,c
and 3
ld (cdir),a
ret
_leftrotate:
sub c
and 3
ld (cdir),a
ret
SumNibBits:
;Thank you, Runer112, for this routine
;returns the sum of the lower 4 bits of A
;output: A = sum of bits
;destroys HL
and %00001111
ld hl,SumNibBits_LUT
add a,l
ld l,a
ld a,(hl)
ret nc
inc h
ld a,(hl)
ret
SumNibBits_LUT:
.db 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4
;.db 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5
getPixelByte:
;standard first part of a getPixel routine. Retrieves the byte of the pixel in HL
ld a,h
ld h,0
ld d,h
ld e,l
add hl,hl
add hl,de
add hl,hl
add hl,hl
ld e,a
srl e
srl e
srl e
add hl,de
ld de,PlotSScreen
add hl,de
ret
getPixel:
;just a getPixel routine. Nothing to see here.
call getPixelByte
and 7
ld b,a
ld a,$80
ret z
rrca
djnz $-1
ret
paintCur:
;fills the current pixel (cx,cy) and sets the "bool_filled" flag
ld hl,(cx)
call getPixel
or (hl)
ld (hl),a
set bool_filled,(iy)
ret
getEdgePixels:
;get all 8 surrounding pixels and put them into A in the order specified at the "bounds" label.
push hl ;save x,y for checking offset later
call getPixelByte
push hl
pop ix
and 7
jr z,_specLeft
cp 7
jr z,_specRight
dec a ;get the surrounding bits into the 3 msb of C, D, and E
ld b,a
ld d,(ix-12)
ld e,(ix+12)
ld a,(hl)
jp z,CheckOffScreen
ld c,b
ld a,e
rrca
djnz $-1
ld e,a
ld b,c
ld a,d
rrca
djnz $-1
ld d,a
ld b,c
ld a,(hl)
rrca
djnz $-1 ;d=ABC00000;a=DXE00000; e=FGH00000
ld c,a
jp CheckOffScreen
_specLeft: ;special-case for left-side overflow
ld d,(ix-12)
ld a,(ix-13)
rra
rr d
ld e,(ix+12)
ld a,(ix+11)
rra
rr e
ld c,(hl)
dec hl
ld a,(hl)
rra
rr c
jp CheckOffScreen
_specRight: ;special-case for right-side overflow
ld d,(ix-11)
ld a,(ix-12)
rl d
rra
rra
rra
ld e,(ix+13)
ld a,(ix+12)
rl e
rra
rra
rra
ld a,(hl)
inc hl
ld c,(hl)
rl c
rra
rra
rra
ld c,a
CheckOffScreen:
pop hl ;recall x,y
ld a,l
dec a
cp 62
jr c,_testx
jr z,_fixtop
jr _fixbtm
_fixtop:
ld e,%11100000
jr _testx
_fixbtm:
ld d,%11100000
_testx:
ld a,h
dec a
cp 94
jr c,EdgePixelCombine
jr z,_fixright
jr _fixleft
_fixright:
set 5,c
set 5,d
set 5,e
jr EdgePixelCombine
_fixleft:
set 7,c
set 7,d
set 7,e
EdgePixelCombine:
;Thank you, Runer112, for this routine
;d=ABC00000
;c=DXE00000
;e=FGH00000
ld a,c
xor d
and %10111111
xor d ;a=DBE00000
rlca
rlca ;a=00DBE000
xor e
and %10111111
xor e ;a=0GDBE000
rrca
rrca ;a=000GDBE0
xor d
and %01011111
xor d ;a=ABCGDBE0
rrca ;a=0ABCGDBE
xor e
and %01011111
xor e ;a=FAHCGDBE
ret
;-----> Copy the gbuf to the screen, guaranteed
;Input: nothing
;Output:graph buffer is copied to the screen, no matter the speed settings
;
;in f,(c) is an unofficial instruction.
;It must be noted that you cannot specify any other register. Only f works.
;You may have to add it in order for the routine to work.
;if addinstr doesn't work, you may manually insert the opcodes .db 0EDh,070h
.addinstr IN F,(C) 70ED 2 NOP 1
SafeCopy:
;di ;DI is only required if an interrupt will alter the lcd.
ld hl,PlotSScreen ;This can be commented out or another entry placed after it
;so the buffer can be provided by option.
ld c,$10
ld a,$80
setrow:
in f,(c)
jp m,setrow
out ($10),a
ld de,12
ld a,$20
col:
in f,(c)
jp m,col
out ($10),a
push af
ld b,64
row:
ld a,(hl)
rowwait:
in f,(c)
jp m,rowwait
out ($11),a
add hl,de
djnz row
pop af
dec h
dec h
dec h
inc hl
inc a
cp $2c
jp nz,col
ret
7
« on: February 01, 2012, 06:58:55 am »
I thought some people might enjoy these.
8
« on: January 18, 2012, 03:23:34 am »
I'll just leave these here. (I'm sure you've seen a few of them already) and one of my personal favorites... Feel free to post more 
9
« on: December 30, 2011, 05:34:22 am »
Hello, everyone. A friend of mine is trying to get some attention for his Kickstarter project, and I thought I'd bring it to this wonderful community. All I can really say is that it would be absolutely wonderful if you guys could spread this around. Other than that I'll let their Kickstarter video speak for itself, but please visit the Kickstarter page as well (link at the bottom). Please read and see more here:
http://www.kickstarter.com/projects/1475020745/meet-the-hugalopes-the-future-of-fluffy-fluffy-fun
10
« on: December 13, 2011, 06:59:47 pm »
I'm working on a project in which I'd like to use some very high precision numbers, but I want to avoid using Apfloat as much as possible because of its slow speed.
After looking around I found a DoubleDouble class, which is written to act as (almost) a Quad precision wrapper using two doubles. It has 106 bits of precision instead of the 113 bits that a real Quad data type would have, but that's fine for me.
But I'm still looking for something with even more precision if possible. I'm wondering how I might have a QuadDouble precision class using 4 doubles for precision, instead of only two. Does anyone know if something of this precision already exists, or how I would go about writing a QuadDouble class if it doesn't already?
11
« on: August 31, 2011, 07:27:04 pm »
I'm working on some pathfinding, and I've been trying to find a good way to divide a map up into sections to use as nodes for high-level pathfinding. Low-level pathing consists of generating the intricate paths required to navigate around obstacles to get to a specified end point, whereas high-level pathing is used to plan out the general route across the map that the low-level path should more or less follow (or at least gravitate toward). High-level pathfinding will ignore small obstacles (like trees or small rocks) and instead focus on finding a general route around any large areas of high ground or large masses of water, or any other major terrain aspects. Another thing that high-level pathfinding should take into account is any major choke points in the map that could be avoided. This can fairly easily be done by simply adding a higher cost for traveling from one node to another if there's a tight choke point in between the two. The actual pathfinding is fairly simple to do. The part I'm running into trouble with is creating the high-level nodes in the first place. Basically I've demonstrated what I'm trying to do on the Xel'Naga Caverns map from StarCraft 2 just as an example:  -Red lines show the actual map walls (ehh, so I scribbled them in...close enough). -Blue lines show where the different sections were divided. -Green dots show the section center points that will act as the actual high-level nodes. To demonstrate how these would be used, let's say you want to find a path from the pink dot to the yellow dot. First you generate a high-level path (blue) from the high-level node of the starting section to the high-level node of the ending section. Then you'll generate the actual low-level path (white) using the high-level path as merely a guide for generally where to go.  I'm trying to figure out a way to generate these map sections dynamically, but I'm really not sure how to go about doing it. Any suggestions? I'm thinking it would work to maybe trace an outline of all the walls and then simplify those outlines to smooth out the chaotic edges and find more of the general shape of the walls, and then use those angles to create the sections, but I'm not sure how to go about simplifying the lines.
EDIT: I found two algorithms that I may be able to use for this: the Ramer-Douglas-Peucker algorithm for simplifying a curve made up of line segments, and the Hertel-Mehlhorn algorithm for approximate convex polygon partitioning. I can use the first algorithm to simplify the walls of the map, then use the second algorithm to remove inessential edges, leaving me with larger convex areas which I can easily use as the nodes. The only thing I still have yet to really find is a good polygon triangulation algorithm that doesn't tend to make slivers...I know Delaunay Triangulation is supposed to avoid long, thin triangles, but I haven't found a very good explanation of the algorithm itself, or any clear implementations of it.
12
« on: August 31, 2011, 12:56:03 pm »
Just a poem I found that really captured me. Thought I'd share.
Phrase Bulimic
by Kathleen Burke
Hello, my name is ___, and
I am a phrase bulimic.
A language rearranger.
Do not proofread your thoughts.
Language-
The real life sustainer-
Tastes better coming up than it does going down
Sautee your words in song
Or scramble them with screams
But let them come; feast on them.
They are delicious.
Delight in their delicious, delectable,
Brutal
Fury.
Relish-
Savor
Anger and love.
Taste how one is a spice to mask
The sweet of the other.
Devour verbs
Fight adverbs fervently for their
Lack of commitment
And win.
Write right.
Bite poems savagely and let their juice
Dribble off your chin onto your
Preying hands.
Make a preposition salsa or a predicate salad,
And top it off with fattening adjectives.
Let the salsa, salsa, and the tangy orange tango.
Write it all down.
This smorgasbord is the soup of Society
Is Civilization
And it rages as your soul licks the bowl clean.
Crave soul food.
In this world of pity, anorexia, starvation-
Never go hungry.
14
« on: August 04, 2011, 08:34:00 pm »
Here's a song I wrote and recorded quite a while ago. It's called "Rickrolled." Guess what it's about. The quality sucks, the singing is bad, but whatever. It was fun to write.  http://soupinabox.com/rickrolled.mp3
15
« on: August 03, 2011, 01:20:07 am »
Have any favorites? For actresses, at least, I like Natalie Portman a lot. Not just because she's very attractive, but because she's also a fantastic actress, and she's very intelligent. Another actress who is also really good and very smart (and looks a lot like Natalie Portman) is Olivia Wilde. Shout-outs also to Emma Stone... ...and, of course, Emma Watson (who DEFINITELY looked better with long hair). For actors, I really appreciate Robin Williams for his inhumanly fast comedic brainpower, and his incredible use of characters and character quirks/eccentricity. I also really like James Franco. He's a very truthful actor, and I really respect that about him. Another incredibly truthful method-actor that I greatly admire is (or was) Heath Ledger. These are only a few of my favorites. What are yours?
|
Show Posts
