tag:blogger.com,1999:blog-69133521226582980522024-02-08T04:33:11.050-08:00Cheesesun WorksOstsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-6913352122658298052.post-24522162978502227822010-10-11T11:08:00.000-07:002010-10-11T11:15:06.380-07:00Code Dump<span class="Apple-style-span" >I've opened up a project on Google Code to host sample code that I write. It's intended to be a repository of files related to blog or forum posts that I write, allowing me to share full source code in a cleaner way that simply including it in the posts themselves. The posts will still include snippets, of course. For now all I have uploaded is the modified code for my <a href="http://cheesesun.blogspot.com/2010/10/basic-cgo-redux.html">Basic cgo</a> article. The entire page is located at <a href="http://code.google.com/p/cheesesuncodedump/">http://code.google.com/p/cheesesuncodedump/</a>.</span>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com0tag:blogger.com,1999:blog-6913352122658298052.post-77987074867643518832010-10-11T09:39:00.000-07:002010-10-11T09:57:59.742-07:00Basic cgo -- Redux!<span class="Apple-style-span" >I happened to notice that my <a href="http://cheesesun.blogspot.com/2009/12/basic-cgo.html">Basic cgo</a> article somehow ended up on go's Google Code page, and I thought that I should make sure my code still works. Some of the information is out of date, such as the files that </span><span class="Apple-style-span" >cgo</span><span class="Apple-style-span" > generates. As for the code: it both does and it doesn't. First off, the Makefile is out of date, so here's a new one:</span><div><span class="Apple-style-span" ><br /></span></div><div><span class="Apple-style-span" ><div><span class="Apple-style-span" >include $(GOROOT)/src/Make.inc</span></div><div><span class="Apple-style-span" ><br /></span></div><div><span class="Apple-style-span" >TARG=gocurses</span></div><div><span class="Apple-style-span" >CGOFILES=gocurses.go</span></div><div><span class="Apple-style-span" >CGO_LDFLAGS=-lncurses</span></div><div><span class="Apple-style-span" ><br /></span></div><div><span class="Apple-style-span" >include $(GOROOT)/src/Make.pkg</span></div><div><span class="Apple-style-span" ><br /></span></div><div><span class="Apple-style-span" >CLEANFILES+=main</span></div><div><span class="Apple-style-span" ><br /></span></div><div><span class="Apple-style-span" >main: install main.go</span></div><div><span class="Apple-style-span" > $(GC) main.go</span></div><div><span class="Apple-style-span" > $(LD) -o $@ main.$O</span></div><div><br /></div><div>Next, linking to ncurses via <span class="Apple-style-span" >cgo</span> currently does not work as a result of <a href="http://code.google.com/p/go/issues/detail?id=667">Issue 667</a>. <span class="Apple-style-span" >6g</span> spits out an "invalid recursive type" error and compilation fails. There is a way to work around this, however.</div><div><br /></div><div>The file where the error occurs is <span class="Apple-style-span" >_cgo_gotypes.go</span>. In it is defined the go equivalents for the C types exposed in <span class="Apple-style-span" >ncurses.h</span>. The problem occurs where <span class="Apple-style-span" >WINDOW</span> is defined. If it is defined below the _win_st struct, <span class="Apple-style-span" >6g</span> spits the error. If it is defined above <span class="Apple-style-span" >_win_st</span>, everything goes well. Fortunately, <span class="Apple-style-span" >cgo</span> will not recreate any files it generates as long as the original source file is unaltered. This allows us to modify any of those generated files and call <span class="Apple-style-span" >make main</span> again in order to continue building the project.</div><div><br /></div><div>With that in mind, the fix is simple:</div><div><ol><li>Run <span class="Apple-style-span" >make main</span> and see the error</li><li>Open <span class="Apple-style-span" >_cgo_gotypes.go</span> and move the line defining <span class="Apple-style-span" >_Ctypedef_WINDOW</span> to above <span class="Apple-style-span" >_Ctype_struct__win_st</span></li><li>Run <span class="Apple-style-span" >make main</span> again</li></ol><div>The program should work from there.</div></div></span></div>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com0tag:blogger.com,1999:blog-6913352122658298052.post-76609710817490100312010-09-05T17:37:00.001-07:002010-09-05T17:42:10.787-07:00Rasterizing Circles and Ellipses<div style="background-color:transparent;font-family:'Times New Roman';margin-left:0px;margin-right:0px"><span id="internal-source-marker_0.13873722031712532" style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">You might recall my post about a fast way of determining what grid squares fit within a circle of a given radius. Beyond the roguelike applications, this algorithm also clearly useful for rasterizing a filled circle. Here’s a modified version of the function:</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">def filled_circle(surface, x0, y0, r, c):</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> for x in range(-r, r+1):</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> dy = int(math.sqrt(r*r - x*x))</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> for y in range(-dy, dy+1):</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+x, y0+y, c)</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">surface</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> is an object with the method <font face="'Courier New'">set</font>, which accepts x and y coordinates and a colour. </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x0</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> and </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y0</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> are the coordinates of the circle’s origin, </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">r</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> is its radius, and </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">c</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> is its colour.</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">The function works by taking advantage of the circle equation: <img alt="x^{2} + y^{2} = r^{2}" class="ee_img tr_noresize" eeimg="1" src="https://www.google.com/chart?cht=tx&chf=bg,s,FFFFFF00&chco=000000&chl=x%5E%7B2%7D%20%2B%20y%5E%7B2%7D%20%3D%20r%5E%7B2%7D" style="vertical-align:middle">. By solving for </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> we get the maximum value for a given </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">, and the function iterates between </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">-y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> and </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">. We can do the same thing for ellipses by substituting the ellipse equation: <img alt="\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1" class="ee_img tr_noresize" eeimg="1" src="https://www.google.com/chart?cht=tx&chf=bg,s,FFFFFF00&chco=000000&chl=%5Cfrac%7Bx%5E2%7D%7Ba%5E2%7D%20%2B%20%5Cfrac%7By%5E2%7D%7Bb%5E2%7D%20%3D%201" style="vertical-align:middle">, where a is half the width of the ellipse and b is half the height. Solving for y, we get the function:</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">def filled_ellipse(surface, x0, y0, a, b, c):</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> for x in range(-a, a+1):</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> dy = int(math.sqrt(b*b * (1.0 - float(x*x)/float(a*a))))</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> for y in range(-dy, dy+1):</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+x, y0+y, c)</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">That’s not a big change.</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">An unfilled circle uses a rather different algorithm. If all we did was take the filled circle algorithm and for each </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> set pixels at </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">dy</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> and </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">-dy</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">, one would find that some pixels are missing. This occurs in cases where there is more than one pixel for a given </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">. We could account for these by swapping </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> and </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> in the function, but that results in plenty of redundant pixel setting. Our goal is to set any given pixel only once.</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">A better method requires than one only finds the pixels for one-eighth of the circle and then rotate all of those pixels to find the rest of the circle. This is simply done by going through all positive and negative combinations for the given coordinate. For example, for </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">(10, 1)</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> we also have </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">(-10, 1)</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">, </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">(10, -1)</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">, and </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">(-10, -1)</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">. That’s four eighths of the circle, and the rest are determined by swapping x and y: </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">(1, 10)</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">, </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">(-1, 10)</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">, </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">(1, -10)</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">, and </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">(-1, -10)</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">.</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">Now the only issue is finding that eighth of a circle. This is done in a similar way to finding the pixels in a filled circle. We iterate through </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> coordinates, calculating the </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> coordinates. We’ve reached an eighth when </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> is equal to or greater than </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">. Unlike the filled circle, we will start at </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">1</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> instead of </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">-r</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">. We could start at </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">0</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">, but by doing that we will set the furthest top, bottom, left, and right pixels more than once. Instead, we will set those before we start the loop. Similarly, we will stop searching for pixels in our eighth before </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> is equal to </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">, otherwise the four more pixels will be set twice. As such, we will set those once, when </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> equals </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">. Thus:</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">def circle(surface, x0, y0, r, c):</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0, y0 + r, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0, y0 - r, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0 + r, y0, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0 - r, y0, c)</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> x = 1</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> while True:</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> y = int(math.sqrt(r*r - x*x))</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> if x < y:</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+x, y0+y, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-x, y0+y, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+x, y0-y, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-x, y0-y, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+y, y0+x, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-y, y0+x, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+y, y0-x, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-y, y0-x, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> else:</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> if x == y:</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+x, y0+y, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-x, y0+y, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+x, y0-y, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-x, y0-y, c)</font></font></font></span></div><div style="background-color:transparent;font-family:'Times New Roman';margin-left:0px;margin-right:0px"><font size="3"><font face="'courier new'"> break<br></font></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> x += 1</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">There’s a lot of lines there, but it’s mostly just pixel setting. The actual algorithm is quite simple.</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">Ellipses follow a similar path, but not as simple. Like with circles, one does not have to calculate the entire shape. However, since ellipses are only symmetrical about two axes, we must find an entire quarter.</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">Recall what I mentioned about the use of the filled circle algorithm for determining the edge. If we used that, the result is missing pixels. Thus, when we come to the point at which pixels might be missing, we switch to iterating over the </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> axis.</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">Determining the point to switch over is not simple. With circles it would be the halfway point, where </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> equals </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">. With an ellipse that point is variable save for one constant: the point where the tangent is </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">45</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> degrees. Another way of putting it is where the slope is </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">1</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> or </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">-1</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">.</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">Calculus tells us that the derivative of a function presents us with a function representing the slope of the original. Thus we solve for </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">y</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> in the ellipse equation and take the derivative of the result. I will not go into the steps involved (mostly because my calculus is rusty and I found a website to do it for me). It suffices to say that when the slope for a given </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">x</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3"> is equal to or less than </font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">-1.0</font></font></font></span><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">, we switch.</font></font></font></span><font size="3"><br></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3">def ellipse(surface, x0, y0, a, b, c):</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0, y0+b, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0, y0-b, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+a, y0, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-a, y0, c)</font></font></font></span></div><div style="background-color:transparent;font-family:'Times New Roman';margin-left:0px;margin-right:0px"><font size="3"><br></font></div><div style="background-color:transparent;font-family:'Times New Roman';margin-left:0px;margin-right:0px"><font size="3"><font face="'courier new'"> y = 0<br></font></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> for x in range(1, a):</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> y = int(math.sqrt(b*b * (1.0 - float(x*x)/(float(a*a))))</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> if -b * x / (a * math.sqrt(a*a - x*x)) < -1:</font></font></font></span></div><div style="background-color:transparent;font-family:'Times New Roman';margin-left:0px;margin-right:0px"><font size="3"><font face="'courier new'"> break<br></font></font><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+x, y0+y, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-x, y0+y, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+x, y0-y, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-x, y0-y, c)</font></font></font></span><font size="3"><br></font> <font size="3"><br></font></div><div style="background-color:transparent;font-family:'Times New Roman';margin-left:0px;margin-right:0px"><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> for dy in range(1, y+1):</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> dx = int(math.sqrt(a*a*(1.0 - float(dy*dy)/float(b*b))))</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+dx, y0+dy, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-dx, y0+dy, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0+dx, y0-dy, c)</font></font></font></span><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="'courier new'"><font color="#000000"><font size="3"> surface.set(x0-dx, y0-dy, c)</font></font></font></span></div><div style="background-color:transparent;font-family:'Times New Roman';margin-left:0px;margin-right:0px"><font size="3"><br></font><span style="font-style:normal;vertical-align:baseline"><font face="verdana"><font color="#000000"><font size="3">That’s it and without setting any pixel more than once.</font></font></font></span></div><br>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com2tag:blogger.com,1999:blog-6913352122658298052.post-26683561862731914322010-08-11T10:35:00.001-07:002010-08-11T11:24:26.790-07:00Circular Number System in C<span class="Apple-style-span" style="font-family:verdana;">In a previous post I discussed the idea of a circular number system. To reiterate: it is a system whereby the passing the maximum value will return one to the beginning. Take a twenty-four hour clock, for example, which has the range of [0, 23]. The hour that is two hours beyond 23 is not 25, but 1.</span><div><span class="Apple-style-span" style="font-family:verdana;"><br /></span></div><div><span class="Apple-style-span" style="font-family:verdana;">Another example is angle measurement. If one has two angles, one at 5 degrees and another at 355 degrees, how far is the second from the first. Linear measurement has one subtracting the two, resulting in an answer of 350 degrees, but looking at the two angles marked on a circle one can see that that is not entirely correct. It is </span><i><span class="Apple-style-span" style="font-family:verdana;">a</span></i><span class="Apple-style-span" style="font-family:verdana;"> distance and in some situations has value, but it is not the shortest distance. For that, the correct answer is -10 degrees.</span></div><div><span class="Apple-style-span" style="font-family:verdana;"><br /></span></div><div><span class="Apple-style-span" style="font-family:verdana;">The implementation of this system that I posted was written in Python, but different programming languages have different behaviours for the modulo operator. In some cases, like C++, the behaviour depends upon the implementation. I will not discuss these differences here, as more knowledgeable individuals have already done so elsewhere. For the purpose of this article, I refer to the default C standard used by gcc under Ubuntu 10.04 Linux.</span></div><div><span class="Apple-style-span" style="font-family:verdana;"><br /></span></div><div><span class="Apple-style-span" style="font-family:verdana;">One further difference between C and Python is that Python's modulo operator also works with floating point numbers, while in C it works only with integers. For floating point numbers one must use <span class="Apple-style-span" style="font-family:'courier new';">fmod</span>, which is found in <span class="Apple-style-span" style="font-family:'courier new';">math.h</span>.</span></div><div><span class="Apple-style-span" style="font-family:verdana;"><br /></span></div><div><span class="Apple-style-span" style="font-family:verdana;">Here is the difference function in C:</span></div><div><span class="Apple-style-span" style="font-family:verdana;"><br /></span></div><div><div><span class="Apple-style-span" style="font-family:'courier new';">double diff(double x0, double x1) {</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> double r = fmod(x1 - x0 + 0.5*UPPER, UPPER);</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> return (r <></span></div><div><span class="Apple-style-span" style="font-family:'courier new';">}</span></div></div><div><span class="Apple-style-span" style="font-family:verdana;"><br /></span></div><div><span class="Apple-style-span" style="font-family:verdana;">The function finds the shortest distance to <span class="Apple-style-span" style="font-family:'courier new';">x1</span> from <span class="Apple-style-span" style="font-family:'courier new';">x0</span> distance, assuming a range of <span class="Apple-style-span" style="font-family:'courier new';">[0, UPPER)</span>. The maximum absolute distance between any two values will never be more than half of <span class="Apple-style-span" style="font-family:'courier new';">UPPER</span>.</span></div>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com1tag:blogger.com,1999:blog-6913352122658298052.post-44717688631139860942010-05-21T19:18:00.000-07:002010-05-22T20:22:02.619-07:00The Heritage UniverseLooking back, there were two authors whose works enticed me to stop selecting random books based on their titles and focus instead on individual writers. One is Piers Anthony, whose <b>Bio of a Space Tyrant</b> series I read when I was sixteen. Briefly, I can describe that series as a combination of science fiction adventure and a dose of the erotic -- which is everything a sixteen year-old boy could want. The other author was Charles Sheffield, whose novel <b>Summertide</b> helped me break away from the science fantasy of so much other books under the "sci-fi" genre and into hard(er) science fiction.<div><br /></div><div>There is no single aspect of <b>Summertide</b> that piqued my interest, but a combination. As I mentioned, it falls into the sub-genre of hard science fiction, whose "science" is generally based in some way on modern theories. Given the distance into the future <b>Summertide</b> takes place, this is difficult to apply to much of the technology involved, but there is enough that it has the feeling of possibility.</div><div><br /></div><div>There is also the milieu of alien species, which is certainly not new to me in science fiction, but the range of shapes was. No species is humanoid save for Humanity itself. For somewhat whose introduction to science fiction came in the form of <b>Star Trek</b> and <b>Star Wars</b> this was something very special indeed.</div><div><br /></div><div>Finally there is the Builders, the ancient and unbelievably advanced species and the mindbogglingly enormous artifacts that they left behind. Sure, <b>Babylon 5</b>, had such beings as the Vorlons and the Shadows, but while their motives might seem enigmatic, they remained clearly active participants in the interstellar scene. The Builders are never truly revealed and even their sentient creations have little useful to say about their creators' nature. This mystery is the basic premise of the series.</div><div><br /></div><div><div>Interestingly, there is no real antagonist in any of the books. The conflict has more to do with the dangerous situations the environments present than anything else. One might argue that the Zardalu (an alien species in the series) were at times the antagonists. In two of the books this is in a way literally true, but I found them presented more as players in a scene written by others (namely the Builders). They acted antagonistic towards the protagonists, but they were never the main issue. The result is that throughout the series the theme is not simply one of overcoming other individuals (though that does happen), but one of exploration and learning.</div></div><div><br /></div><div>As for the author himself, Sheffield may not be the greatest author I have read. His narrative lacked the flowing introspective style presented by authors such as Stephen R. Donaldson or the sweeping epic style of those such as Glen Cook, but it was not a bad style, either. His writing was competent and his characterisations were convincing. He understood how to write about people and given them personalities that felt real and possible to empathise with. This is really basic stuff when it comes to writing fiction, but I have read several books whose authors proved unable to do this (or unable to do it more than once, merely repeating the same characterisations under different names in each book). Basically, I never found myself at odds with the author, while at the same time wishing better for the story. Charles Sheffield was simply a good author.</div><div><br /></div><div>Over a decade after reading the first volume, I have finally read the final one: <b>Resurgence</b>. I purchased the entire series via <a href="http://www.blogger.com/www.webscription.net">WebScription.net</a> and read it start to finish. It is just as good a series as I remembered it.</div><div><br /></div><div>It is unfortunate that Sheffield died the year the final volume was published. It ends with a newly discovered threat and a inference that a new set of protagonists would take over. I have to wonder if this was Sheffield's own indication that the series should continue with new blood directing it, knowing that he might not be able to do so himself. The series never gained the popularity that such iconic works as Isaac Asimov's <b>Robot</b> and <b>Foundation</b> series had, though, so such a future is in doubt. Ultimately, everything is left to the readers' imaginations.</div>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com0tag:blogger.com,1999:blog-6913352122658298052.post-60350460705103585172010-04-24T21:42:00.001-07:002010-04-24T21:44:34.323-07:00Callbacks with cgo<div>A major limitation of cgo is the lack of support for callbacks or, in more general terms, the ability for C to call a Go function. This is a major issue for bindings to event driven systems. As part of impending support for SWIG, however, the Go team has expanded cgo to provide a facility by which Go functions may be exposed to C.</div><br><div>In one's cgo files, exposing a function is a very simple matter: one precedes the function header with a comment starting with the word export and followed by the function name. For example:</div><br><div><font face="'Courier New'">//export Foo</font></div><div><font face="'Courier New'">func Foo() {</font></div><div><font face="'Courier New'"> // ...</font></div><div><font face="'Courier New'">}</font></div><br>When cgo sees this it generates two new C files: <font face="'Courier New'">_cgo_export.c</font> and <font face="'Courier New'">_cgo_export.h</font>. These files provide the wrappers that enable a C program to call Go functions.<br><br><div>Provided with the current distribution of Go is an example program demonstrating this new feature. It is found in:</div><br><div><font face="'Courier New'">$GOBIN/misc/cgo/life</font><br></div><br><div>Looking through that example, though, one should notice one problem: it is not an example classic callbacks. That is, Go is not passing functions to C. Instead, the functions are merely being exposed so that C can call them. Thus the problem remains for event driven libraries such as GLUT. Callbacks are achieved via a bit of indirection.</div><br>Let us start by creating a very simple library that adds number via a callback. It has a single function, call_add, which takes a function pointer and calls it to add two integers.<br><br><div><font face="'Courier New'">// calladd.h</font></div><br><div><font face="'Courier New'">typedef int(*adder)(int, int);</font></div><br><div><font face="'Courier New'">extern void call_add(adder);</font></div><br><div><font face="'Courier New'">//callback.c</font></div><br><div><font face="'Courier New'">#include <stdio.h></font></div><div><font face="'Courier New'">#include "calladd.h"</font></div><br><div><font face="'Courier New'">void</font></div><div><font face="'Courier New'">call_add(adder func) {</font></div><div><font face="'Courier New'"> printf("Calling adder\n");</font></div><div><font face="'Courier New'"> int i = func(3, 4);</font></div><div><font face="'Courier New'"> printf("Adder returned %d\n", i);</font></div><div><font face="'Courier New'">}</font></div><br>Nothing to it. Compile it and turn it into a shared object:<br><br><div><font face="'Courier New'">gcc -g -c -fPIC calladd.c</font></div><div><font face="'Courier New'">gcc -shared -o calladd.so calladd.o</font></div><br>Now here's the interesting part: in order to pass a Go function to C we must create a wrapper that passes the wrapper to the Go function. Wonderful, eh? Two levels of indirection. . .<br><br><div><font face="'Courier New'">// funcwrap.h</font></div><br><div><font face="'Courier New'">extern void pass_GoAdd(void);</font></div><br><div><font face="'Courier New'">// funcwrap.c</font></div><br><div><font face="'Courier New'">#include "_cgo_export.h"</font></div><div><font face="'Courier New'">#include "calladd.h"</font></div><br><div><font face="'Courier New'">void</font></div><div><font face="'Courier New'">pass_GoAdd(void) {</font></div><div><font face="'Courier New'"> call_add(&GoAdd);</font></div><div><font face="'Courier New'">}</font></div><br>Our cgo file is rather simple:<br><br><div><font face="'Courier New'">//callback.go</font></div><br><div><font face="'Courier New'">package callback<br><br></font><div><font face="'Courier New'">// #include "callgo.h"</font></div><div><font face="'Courier New'">// #include "funcwrap.h"</font></div><div><font face="'Courier New'">import "C"</font></div><br><div><font face="'Courier New'">func Run() {</font></div><div><font face="'Courier New'"> // call the wrapper<br></font></div><div><font face="'Courier New'"> C.pass_GoAdd()</font></div><div><font face="'Courier New'">}</font></div><br><div><font face="'Courier New'">//export GoAdd</font></div><div><font face="'Courier New'">func GoAdd(a, b int) int {</font></div><div><font face="'Courier New'"> return a + b</font></div><div><font face="'Courier New'">}</font></div></div><br>This is still not really a callback, as we are not passing an arbitrary function. That would require yet another level of indirection (for a total of three), whereby we store a function pointer and call it within GoAdd. Hopefully in the future one level will be removed. I suspect that this could be possible if cgo interpreted any passing of an exported function to a C function as passing the wrapper, but I cannot say that I have looked deeply into the matter.<br><br><div>To conclude, here's the Makefile for this project (a modified version of the life example's):</div><br><div><font face="'Courier New'">CGO_LDFLAGS=_cgo_export.o calladd.so funcwrap.so $(LDPATH_linux)</font></div><div><font face="'Courier New'">CGO_DEPS=_cgo_export.o calladd.so funcwrap.so</font></div><br><div><font face="'Courier New'">CLEANFILES+=main</font></div><br><div><font face="'Courier New'">include $(GOROOT)/src/Make.pkg</font></div><br><div><font face="'Courier New'">funcwrap.o: funcwrap.c _cgo_export.h</font></div><div><font face="'Courier New'"> gcc $(_CGO_CFLAGS_$(GOARCH)) -g -c -fPIC $(CFLAGS) funcwrap.c</font></div><br><div><font face="'Courier New'">funcwrap.so: funcwrap.o</font></div><div><font face="'Courier New'"> gcc $(_CGO_CFLAGS_$(GOARCH)) -o $@ funcwrap.o $(_CGO_LDFLAGS_$(GOOS))</font></div><br><div><font face="'Courier New'">main: calladd.so install main.go</font></div><div><font face="'Courier New'"> $(GC) main.go</font></div><div><font face="'Courier New'"> $(LD) -o $@ main.$O</font></div><br>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com2tag:blogger.com,1999:blog-6913352122658298052.post-44909813978847941392010-03-21T18:37:00.001-07:002010-03-21T19:16:00.897-07:00Grid Squares in a Circle<span class="Apple-style-span" style="font-family:georgia;">I know that it's a minor operation, but for a long time I couldn't help but wonder if there were an optimized way of finding out which squares in a grid fall within a given radius. However, because it is such a minor operation and because the brute force method works adequately, I never actually went out of my way to try and solve this problem -- until now. Boredom is a wonderful thing. . .</span><div><span class="Apple-style-span" style="font-family:georgia;"><br /></span></div><div><span class="Apple-style-span" style="font-family:georgia;">First off, the brute force approach:</span></div><div><span class="Apple-style-span" style="font-family:georgia;"><br /></span></div><div><span class="Apple-style-span" style="font-family:georgia;">Given an origin </span><span class="Apple-style-span" style="font-family:'courier new';">(x0, y0)</span><span class="Apple-style-span" style="font-family:georgia;"> and a radius <span class="Apple-style-span" style="font-family:'courier new';">r</span>, the maximum orthogonal extents of a circle is equal to </span><span class="Apple-style-span" style="font-family:'courier new';">(x0±r, y0±r)</span><span class="Apple-style-span" style="font-family:georgia;">. Given those extents, coordinates whose distance from the origin are less than or equal to the radius are within the circle.</span></div><div><span class="Apple-style-span" style="font-family:georgia;"><br /></span></div><div><span class="Apple-style-span" style="font-family:georgia;"><div><span class="Apple-style-span" style="font-family:'courier new';">def brute_coords(r):</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> coords = []</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"><br /></span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> for y in range(-r, r+1):</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> for x in range(-r, r+1):</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> if math.hypot(x, y) <= r:</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> coords.append((x, y))</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"><br /></span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> return coords</span></div><div><br /></div></span></div><div><span class="Apple-style-span" style=" ;font-family:georgia;">Very easy and with relatively small circles it is sufficiently fast. However, there should be a way to do this without even considering squares outside of the circle. There is and the solution comes thanks to the Pythagorean Theorem. Specifically, the circle's radius is the hypotenuse of a triangle and the distance along the x-axis is another length. The number of squares above and below that axis is equal to the final length. Thus we iterate along the minimum and maximum x-coordinates and calculate the verticals.</span></div><div><span class="Apple-style-span" style=" ;font-family:georgia;"><br /></span></div><div><span class="Apple-style-span" style=" ;font-family:georgia;"><div><span class="Apple-style-span" style="font-family:'courier new';">def smart_coords(r):</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> coords = []</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> </span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> for x in range(-r, r+1):</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> dy = int(math.sqrt(r*r - x*x))</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> for y in range(-dy, dy+1):</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> coords.append((x, y))</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> </span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> return coords</span></div><div><br /></div><div>With small radii, such as a character's vision radius in a roguelike, the performance difference is a few milliseconds at most, on my system. With a radius of 100, <span class="Apple-style-span" style="font-family:'courier new';">smart_coords</span> is twice as fast. At 1000, it takes 12 seconds, while <span class="Apple-style-span" style="font-family:'courier new';">brute_coords</span> takes 17. That's pretty good!</div><div><br /></div><div>As for whether the optimization is worthwhile in practical applications, I have no idea. I haven't made any real comparison and probably won't bother to. I will use it, though, if for no other reason than because it is better and it is not a very complex solution.</div></span></div>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com2tag:blogger.com,1999:blog-6913352122658298052.post-60335261806322299692010-01-10T10:57:00.000-08:002010-01-10T15:25:41.081-08:00Go, syscall, and inotify<p><span style="font-family:verdana;">At the time of writing this article, Go does not implement all of the syscalls for which it has constants. One of these is inotify, which allows one to monitor file system events. It, and similar libraries are what allow file managers such as KDE's Dolphin or Gnome's Nautilus to almost immediately show a file's new date-stamp when it has been modified.</span></p><p><span style="font-family:verdana;">For information on inotify, check out the following article at LinuxJournal.com:<br /></span></p><p><span style="font-family:verdana;">http://www.linuxjournal.com/article/8478<br /></span></p><p><span style="font-family:verdana;">Fortunately, Go's </span><span style="font-family:courier new;">syscall</span><span style="font-family:verdana;"> package exports the low-level function that it uses for all implemented syscalls. This function is named, appropriately, </span><span style="font-family:courier new;">Syscall</span><span style="font-family:verdana;">. There is also </span><span style="font-family:courier new;">Syscall6</span><span style="font-family:verdana;">, which receives six arguments (in addition to the syscall id) instead of three. For our purposes, </span><span style="font-family:courier new;">Syscall</span><span style="font-family:verdana;"> will be sufficient.</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">First, the basics:</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:courier new;">Syscall</span><span style="font-family:verdana;"> receives and returns all values as the type </span><span style="font-family:courier new;">uintptr</span><span style="font-family:verdana;">. This seems strange and at a glance would seem to indicate that it deals with pointers to all values, but that is actually not necessarily the case. Integers, for example, are simply converted directly via a cast.<br /></span></p><p><span style="font-family:courier new;">param := uintptr (num)</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">Strings, however, are a slightly more complex affair, but the </span><span style="font-family:courier new;">syscall</span><span style="font-family:verdana;"> package provides a necessary function, </span><span style="font-family:courier new;">StringBytePtr</span><span style="font-family:verdana;">, which simply converts the string to a byte slice and returns a pointer to the first element.<br /></span></p><p><span style="font-family:courier new;">param := uintptr (unsafe.Pointer (StringBytePtr (str)))</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">Although </span><span style="font-family:courier new;">Syscall</span><span style="font-family:verdana;"> must receive three values (in addition to the syscall id), if the particular syscall requires less, one simply passes 0 to the remainder. Similarily, it always returns three values, though not all are meaningful. All are of the type </span><span style="font-family:courier new;">uintptr</span><span style="font-family:verdana;">: the first two being the actual return values, while the last is an error code. Values that are not needed may be received as an empty variable: </span><span style="font-family:courier new;">_</span><span style="font-family:verdana;">.</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">The </span><span style="font-family:courier new;">os</span><span style="font-family:verdana;"> package contains the functionality needed to print syscall error codes. </span><span style="font-family:courier new;">os.NewSyscallError</span><span style="font-family:verdana;"> receives a string and an integer. The first should be the name of the syscall you attempted, while the last is the error code that </span><span style="font-family:courier new;">Syscall</span><span style="font-family:verdana;"> returned (casted to </span><span style="font-family:courier new;">int</span><span style="font-family:verdana;">, of course). The structure returned implements </span><span style="font-family:courier new;">os.Error</span><span style="font-family:verdana;">.<br /></span></p><p><span style="font-family:verdana;">In C inotify consists of three functions: </span><span style="font-family:courier new;">inotify_init</span><span style="font-family:verdana;">, </span><span style="font-family:courier new;">inotify_add_watch</span><span style="font-family:verdana;">, and </span><span style="font-family:courier new;">inotify_rm_watch</span><span style="font-family:verdana;">. The corresponding syscall ids are </span><span style="font-family:courier new;">SYS_INOTIFY_INIT</span><span style="font-family:verdana;">, </span><span style="font-family:courier new;">SYS_INOTIFY_ADD_WATCH</span><span style="font-family:verdana;">, and </span><span style="font-family:courier new;">SYS_INOTIFY_RM_WATCH</span><span style="font-family:verdana;">. Given the above information, it is simple to call each. For example:</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:courier new;">fd , _, errptr = syscall.Syscall (syscall.SYS_INOTIFY_INIT, 0, 0, 0);<br />if err = os.NewSyscallError ("SYS_INOTIFY_INIT", int (errptr)); err != nil {<br /> // deal with the error<br />}<br /><br /></span><span style="font-family:verdana;">The first returned variable </span><span style="font-family:courier new;">fd</span><span style="font-family:verdana;"> is the file descriptor, the second is ignored, and the la</span><span style="font-family:verdana;">st is the error code.</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:courier new;">pth := "/home/ostsol/Programming/Go/notify/blah.txt"<br />str := uintptr (unsafe.Pointer (syscall.StringBytePtr (pth)));<br />wd, _, errptr = syscall.Syscall (syscall.SYS_INOTIFY_ADD_WATCH,<br /> uintptr (fd), str, 0x00000002);<br />if err = os.NewSyscallError ("SYS_INOTIFY_ADD_WATCH", int (errptr)); err != nil {<br /> //deal with the error<br />}</span><br /></p><p><span style="font-family:verdana;">Unfortunately, Go does not expose the event masks for inotify. </span><span style="font-family:courier new;">0x00000002</span><span style="font-family:verdana;"> is the mask for the modify event.<br /></span></p><p><span style="font-family:verdana;">The event can be read via </span><span style="font-family:courier new;">syscall.Read</span><span style="font-family:verdana;">, which receives the file descriptor (casted to </span><span style="font-family:courier new;">int</span><span style="font-family:verdana;">) and an empty byte buffer. The inotify event structure is, of course, not implemented in Go, so one has to create one's own:<br /></span></p><p><span style="font-family:courier new;">type NotifyEvent struct {<br /> Wd int32;<br /> Mask uint32;<br /> Cookie uint32;<br /> Len uint32<br />}</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">Decoding the buffer filled by </span><span style="font-family:courier new;">syscall.Read</span><span style="font-family:verdana;"> is accomplished via the </span><span style="font-family:courier new;">encoding/binary</span><span style="font-family:verdana;"> package. The </span><span style="font-family:courier new;">binary.Read</span><span style="font-family:verdana;"> function expects a type that fulfills the </span><span style="font-family:courier new;">io.Reader</span><span style="font-family:verdana;"> interface, which one can create via the </span><span style="font-family:courier new;">NewReader</span><span style="font-family:verdana;"> function in the </span><span style="font-family:courier new;">strings</span><span style="font-family:verdana;"> package.</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">The original </span><span style="font-family:courier new;">inotify_event</span><span style="font-family:verdana;"> structure exposed via the C header </span><span style="font-family:courier new;">sys/inotify.h</span><span style="font-family:verdana;"> also contains a </span><span style="font-family:courier new;">name</span><span style="font-family:verdana;"> field. You'll notice that its type is </span><span style="font-family:courier new;">char[0]</span><span style="font-family:verdana;">. We did not add this field to our structure because </span><span style="font-family:courier new;">binary.Read</span><span style="font-family:verdana;"> would try to find a value to put in it. The value only exists if the </span><span style="font-family:courier new;">Len</span><span style="font-family:verdana;"> field is greater than zero. If it is, we can extract the string from the byte buffer manually.<br /></span></p><p><span style="font-family:courier new;">chars := make ([]byte, 80);<br />ln, errno := syscall.Read (fd, chars);<br />if err = os.NewSyscallError ("SYS_READ", errno); err != nil {<br /> // deal with it<br />}<br /><br />event := new (NotifyEvent);</span></p><p><span style="font-family:courier new;">reader := strings.NewReader (string (chars[0:]));<br />if err = binary.Read (reader, binary.LittleEndian, event); err != nil {<br /> // deal with it<br />}<br /><br />fmt.Println ("Event:");<br />fmt.Printf ("\twd: %d\n\tmask: %d\n\tcookie: %d\n\tlen %d\n",<br /> event.Wd, event.Mask >> 16, event.Cookie, event.Len);<br /><br />if event.Len > 0 {<br /> fmt.Printf ("\tname: %s", string (chars[16:16+event.Len]))<br />}</span></p><p><span style="font-family:verdana;">In a real system, multiple events may be returned by </span><span style="font-family:courier new;">syscall.Read</span><span style="font-family:verdana;">. Thus, the buffer may have to be much larger and one will have to iterate through it, each time creating a reader further along in the buffer.<br /></span></p><p><span style="font-family:courier new;">event := new (NotifyEvent);<br /><br />for i := uint32 (0); i < uint32 (ln); i += 16 + event.Len {<br /> reader := strings.NewReader (string (chars[i:]));<br /> // ...<br /> }<br /></span></p><p><span style="font-family:verdana;">There are two problems that I encountered in the creation of this article. First is the </span><span style="font-family:courier new;">event.Mask</span><span style="font-family:verdana;"> field. The value it returns is </span><span style="font-family:courier new;">32768</span><span style="font-family:verdana;">, which is not the flag that I input via </span><span style="font-family:courier new;">SYS_NOTIFY_ADD_WATCH</span><span style="font-family:verdana;">. Secondly, using </span><span style="font-family:courier new;">SYS_NOTIFY_RM_WATCH</span><span style="font-family:verdana;"> tosses me an 'invalid argument' error. Thinking it was a Go problem, I re-wrote the program in C, but the same issues occurred. It's strange, but everything else I did works solidly. Hopefully this article helps despite the issues.</span><span style="font-family:verdana;"><br /></span></p>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com1tag:blogger.com,1999:blog-6913352122658298052.post-75020705151762347022009-12-12T21:05:00.000-08:002010-01-17T10:57:46.918-08:00Basic cgo<p><span style="font-family:verdana;">Go has provided within its distribution a couple of examples to describe how one uses cgo, the command line utility that one uses to interact with C libraries. Beyond that there is practically no official documentation, perhaps due to the Go team's desire to encourage the development of native Go libraries. However, not everyone is particularly keen on reinventing the wheel, making cgo rather important.</span></p><p><span style="font-family:verdana;">In this article I will try to describe how one would go about linking to a C library. My example will basically be the cgo equivalent of an ncurses "Hello, world" program. It provides several basics about cgo usage: interacting with C libraries, calling and passing parameters to C functions, and the Makefile.</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">First off, the very basics:<br /></span></p><p><span style="font-family:courier new;">package gocurses <br /></span></p><span style="font-family:courier new;"><br />/*<br />#include <ncurses.h><br />import "C"<br />*/<br /></span></p><p><span style="font-family:verdana;">"C" is not actually a real package. It is merely a signal to cgo that the lines commented immediately prior to the import statement are to be compiled as C code and that their contents are to be accessible to the succeeding Go code. Here we are including the ncurses header. The functions, types, and variables exposed in that header are accessed as if they existed in the "C" package. Thus, to create the ncurses window, we call:</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:courier new;">C.initscr ();</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">Here's the entire program, which I will subsequently explain:</span></p><p><span style="font-family:courier new;">package gocurses<br /><br />/*<br />#define NCURSES_ENABLE_STDBOOL_H 0<br /><br />#include <ncurses.h><br />#include <stdlib.h><br /><br />int Printw (const char* str) { return printw (str); }<br />*/<br />import "C"<br /><br />import (<br /> "fmt";<br /> "unsafe"<br />)<br /><br />func Hello (s string) {<br /> C.initscr ();<br /><br /> p := C.CString (fmt.Sprintf ("Hello, %s", s));<br /> C.Printw (p);<br /> C.free (unsafe.Pointer (p));<br /><br /> C.refresh ();<br /> C.getch ();<br /> C.endwin ()<br />}</span><br /></p><p><span style="font-family:verdana;">Starting from the beginning, the macro is required due to ncurses handling of the bool type. Do not worry too much about it for the purpose of this example.<br /></span></p><p><span style="font-family:verdana;">Further down we see a wrapper around the ncurses 'printw' function. This is necessary because cgo cannot deal with C's '...' parameter. Fortunately we do not even need it, as it exists in this case merely for string formatting.<br /></span></p><p><span style="font-family:verdana;">Note that I separate the import for "C" from the rest of the imports. This is necessary, as putting it with the rest will (at the time of writing this article) prevent cgo from detecting where our C code is.<br /></span></p><p><span style="font-family:verdana;">Further along we create our 'Hello' function and call 'initscr' to create a new ncurses window, as described earlier. Now we deal with passing strings to C. </span><span style="font-family:verdana;">'C.CString' converts our Go string, 's', into a C-style string. C strings are the only type whose conversion function is prefixed by 'C'. All other types retain their own names. Thus: for C ints, 'C.int'; for C floats, 'C.float'; etc.<br /></span></p><p><span style="font-family:verdana;">We see here why we do not need to worry about the '...' parameter in 'printw'. 'fmt.Sprintf' can perform the formatting we need. There are, perhaps, other uses of the '...' parameter that will require different workarounds, but for the purpose of this example we need not worry about them.<br /></span></p><p><span style="font-family:verdana;">After calling Printw, we need to free the memory used by our new C string. It is, after all, simply an array of chars created on the heap and we do not want a memory leak. This is why we included 'stdlib.h': for the 'free' function. 'free' receives a pointer to void, a type that does not exist in Go. 'unsafe.Pointer' returns a compatible type, though.</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">The rest of the program is fairly basic. Here's our main.go:</span></p><p><span style="font-family:courier new;">package main<br /><br />import "gocurses"<br /><br />func main () {<br /> gocurses.Hello ("world")<br />}</span><br /></p><p><span style="font-family:verdana;">Now, we still need to compile everything. W</span><span style="font-family:verdana;">e'll use a Makefile, as there a fair number of steps to compiling a cgo file.<br /></span></p><p><span style="font-family:verdana;"><br /></span><span style="font-family:courier new;">include $(GOROOT)/src/Make.$(GOARCH)<br /><br />PKGDIR=$(GOROOT)/pkg/$(GOOS)_$(GOARCH)<br /><br />TARG=gocurses<br />CGOFILES=gocurses.go<br />CGO_LDFLAGS=-lncurses<br /><br />include $(GOROOT)/src/Make.pkg<br /><br />CLEANFILES+=main $(PKGDIR)/$(TARG).a<br /><br />main: install main.go<br /> $(GC) main.go<br /> $(LD) -o $@ main.$O</span><span style="font-family:courier new;"><br /></span></p><p><span style="font-family:verdana;">The first line includes a file that simply defines some variables: CC, GC, LD, and O. These define the compilers, the linker, and the file extension used for your platform. On a 32-bit x86 platform, the values would be 8c, 8g, 8l, and .8, respectively. On an amd64 platform, they would be 6c, 6g, 6l, and .6.</span><span style="font-family:courier new;"><br /></span></p><p><span style="font-family:verdana;">Next is simply a shortcut to Go's package directory. It makes for less typing in Makefiles for larger projects.<br /></span></p><p><span style="font-family:verdana;">The next five lines are cgo-specific:</span></p><p><span style="font-family:verdana;">TARG defines the name of the module we are compiling. Since we defined it as gocurses in our source, that is the name here.<br /></span></p><p><span style="font-family:verdana;">CGOFILES is a list of all .go files necessary for this module. Since we everything is in a single file, we need only the one.<br /></span></p><p><span style="font-family:verdana;">CGO_LDFLAGS defines any linker flags we need. ncurses is not part of C's standard library, so we must tell cgo to explicitly link to it.<br /></span></p><p><span style="font-family:verdana;">Next we include the file that Go provides to automate the cgo compilation process. Take a look inside, if you wish, but I will not be going very deeply into what it does. I will, however, explain a bit:</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">The cgo command line program creates four new files. In our case they are gocurses.cgo1.go, </span><span style="font-family:verdana;">gocurses.cgo2.go, </span><span style="font-family:verdana;">gocurses.cgo3.c, and </span><span style="font-family:verdana;">gocurses.cgo4.c. The first is a translation of the original gocurses.go into normal go code. The second defines all C types and variables that we used. The third and fourth contain C code that wraps our calls.</span></p><p><span style="font-family:verdana;">When errors occur in the compilation of the Go code in a cgo file, it will often point to lines in *.cgo1.go. Do not edit the contents of that file. Use it as a reference to find where the error is in your .go file.</span><span style="font-family:verdana;"><br /></span></p><p><span style="font-family:verdana;">The actual steps the Makefile performs to compile these four files can be seen when one calls 'make main', though I will not go over them.<br /></span></p><p><span style="font-family:verdana;">Back to the Makefile: CLEANFILES is just a list of files that Make.pkg uses to automatically remove all build files. We add our executable to the list and also the package that it will install.<br /></span></p><p><span style="font-family:verdana;">Finally we compile our main.go. The 'install' directive there is what tells 'make' to actually start compiling our cgo files.</span></p><p><span style="font-family:verdana;">Please note that the final two lines must be indented using tab characters, not spaces. When editing Makefiles you must ensure that your editor uses tabs and does not convert them to spaces.<br /></span></p><p><span style="font-family:verdana;">I use vim and have set it to convert tabs to spaces, since I also code in Python. However, when I need a tab I can create one using by pressing ctrl-v and hitting the tab key.<br /></span></p><p><span style="font-family:verdana;">Well, that's it. In the command line type 'make main' and the program should compile. Run the executable 'main' and "Hello, world" should print. Press any key and the program will exit. Hopefully this little tutorial helps someone.<br /></span></p>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com8tag:blogger.com,1999:blog-6913352122658298052.post-71653028215095067512009-12-06T13:48:00.000-08:002010-01-17T10:57:46.919-08:00Reflection Package in GoWhile Go does not have the level of introspection that allows a language like Python to define new types during runtime, it at least has the ability to examine and manipulate arbitrary types. One can, for example, pass a random object into a function that will identify the object's type and, in the case of a struct, its fields.<br /><br />Indeed, if one looks into the 'fmt' package at the Printf family of functions, we see that Go's implementation of arbitrary parameters (the ... parameter) requires the use of 'reflect' to extract those parameters. Most interesting, however, is the 'xml' package, which contains a function call 'Unmarshal'. Unmarshal parses an xml file and attempts to implant the data into a given struct, matching xml elements with struct fields.<br /><br />Unfortunately, reflection has a major issue: a lack of documentation. All we have to work with is the package specification and the aforementioned examples of the 'fmt' and 'xml' packages to learn from. Furthermore, these examples are rather complex. For this reason, I will make an attempt at producing a series of simple examples.<br /><br />First off, let us have Go identify a parameter of arbitrary type.<br /><br />Go allows one to take a parameter of any type and store it or pass it into a function via the empty interface: 'interface{}'. Since the empty interface defines no methods, all types implement it -- even basic types like integers or booleans. Thus we have the skeleton of our 'Identify' function:<br /><br /><span style="font-family:courier new;">func Identify (val interface{}) {<br /></span><p><span style="font-family:courier new;">}</span></p><p>The first thing that 'reflect' must do for us is turn 'val' into something that the package can work with. The function that does this is NewValue, which takes as a parameter any value and returns a reflection value. Note that the type 'Value' is an interface. This will be more important later.</p><span style="font-family:courier new;">func Identify (val interface{}) {<br /> v := reflect.NewValue (val)<br />}</span><br /><br />From here, the most basic way to identify the type is to simply ask for it via reflect.Value's 'Type' method. This returns a type object, which in turn implements a method call 'Name' that returns a string.<br /><br /><span style="font-family:courier new;">func Identify (val interface{}) {<br /> v := reflect.NewValue (val);<br /> <br /> fmt.Println (v.Type ().Name ())<br />}</span><br /><br />Thus, when we call 'Identify (5)' the output is 'int'. Call 'Identify (Stuff{3})' and the output is 'Stuff'.<br /><br />Not a very useful function except, perhaps, for debugging. Let's try something more complex, like diving into a struct instance to extract all field names and values and print them. Basically, it will be a generic Print function.<br /><br /><span style="font-family:courier new;">type Stuff struct {<br /> Num int;<br /> Str string;<br /> Boo bool<br />}<br /><br />func PrintAny (val interface{}) {<br />}</span><br /><br />We start the same way as with 'Identify', but creating a reflection value. However, to keep things generic and to avoid massive indentation, we'll use PrintAny simply as a feeder for the function that will do the actual work.<br /><br /><span style="font-family:courier new;">func printAny (val reflect.Value) {<br /><br />}<br /><br />func PrintAny (val interface{}) {<br /> v := reflect.NewValue (val);<br /> printAny (v)<br />}</span><br /><span ><br /></span>To start we'll just have printAny deal with basic types. For the sake of simplicity, I'll just deal with the three basic types we'll need for our struct: int, string, and bool. First we'll use an if-statement to determine the type. Since the second value returned by a type assertion tells us whether the cast was successful, we can use that to determine whether we've found the correct type. The cast variable is of a type that implements a function called 'Get', which returns the value of the variable. The basic interface Value does not implement Get because it does not know what type to return.<br /><br /><span style="font-family:courier new;">func printAny (val reflect.Value) {<br /> if v, ok := val.(*reflect.IntValue); ok {<br /> fmt.Printf ("%d\n", v.Get ())<br /> } else if v, ok := val.(*reflect.StringValue); ok {<br /> fmt.Println (v.Get ())<br /> } else if v, ok := val.(*reflect.BoolValue); ok {<br /> fmt.Printf ("%t\n", v.Get ())<br /> } else fmt.Println ("Unknown Type")<br />}</span><span ><br /></span><p>This is the cumbersome way of doing this. I show it simply to demonstrate type assertions with reflect. Now let's simplify it using the ability of the switch-statement to deal with types. This way, we do not have to worry about 'ok'. The switch-statement automatically looks over the cases to decide which is valid, with 'default' handling the final 'else' case.<br /></p><br /><span style="font-family:courier new;">func printAny (val reflect.Value) {<br /> switch v := val.(type) {<br /> case *reflect.IntValue:<br /> fmt.Printf ("%d\n", v.Get ())<br /> case *reflect.StringValue:<br /> fmt.Println (v.Get ())<br /> case *reflect.BoolValue:<br /> fmt.Printf ("%t\n", v.Get ())<br /> default:<br /> fmt.Println ("Unknown Type")<br /> }</span><br /><span style="font-family:courier new;">}</span><br /><p>Thus:<br /></p><span style="font-family:courier new;">func main () {<br /> var num int = 4;<br /> PrintAny (num)<br />}</span><span ><br /></span><p>. . . will output '4'. However, what if we call 'PrintAny (&num)'? It'll run into the default case. Let's get around that.<br /></p>The reflect package handles pointers via the 'PtrValue' type. The value held by the memory pointed to is accessed by PtrValue's 'Elem' method, which returns a generic reflect 'Value'. To get the actual value, we must run it through the switch-statement again, but instead of nesting one, we'll simply recurse by calling printAny again with the result of 'Elem' as the parameter.<br /><br /><span style="font-family:courier new;">func printAny (val reflect.Value) {<br /> switch v := val.(type) {<br /> case *reflect.PtrValue:<br /> if v.IsNil () {<br /> fmt.Println ("nil")<br /> }<br /> printAny (v.Elem ())<br /> case *reflect.IntValue:<br /> fmt.Printf ("%d\n", v.Get ())<br /> case *reflect.StringValue:<br /> fmt.Println (v.Get ())<br /> case *reflect.BoolValue:<br /> fmt.Printf ("%t\n", v.Get ())<br /> default:<br /> fmt.Println ("Unknown Type")<br /> }<br />}</span><br /><span ><br /></span>This is why I separated the bulk of the code from the original PrintAny function.<br /><br />Note that I check to see if the pointer is nil. If I don't, when the function recurses it'll land in the default case.<br /><br />Next is dealing with structs. All structs, regardless of the actual type, are defined by 'reflect.StructValue'. It implements all methods necessary to iterate through its fields and extract their data. The fields are accessed individually by calling the 'Field' method with an index as the parameter. 'Field' returns a basic 'Value', so we can recurse again.<br /><br /><span style="font-family:courier new;">func printAny (val reflect.Value) {<br /> switch v := val.(type) {<br /> case *reflect.PtrValue:<br /> if v.IsNil () {<br /> fmt.Println ("nil")<br /> }<br /> printAny (v.Elem ())<br /> case *reflect.StructValue:<br /> for i := 0; i < v.NumField (); i++ {<br /> printAny (v.Field (i))<br /> }<br /> case *reflect.IntValue:<br /> fmt.Printf ("%d\n", v.Get ())<br /> case *reflect.StringValue:<br /> fmt.Println (v.Get ())<br /> case *reflect.BoolValue:<br /> fmt.Printf ("%t\n", v.Get ())<br /> default:<br /> fmt.Println ("Unknown Type")<br /> }<br />}</span><br /><span ><br /></span>Wait, though: in the introduction to this example I said that I wanted the field names, too. Fortunately 'reflect' allows us to find those via the 'StructType' type. 'StructType' and other '*Type' types in 'reflect' provide information on the type itself. In the case of structs, this includes information on the fields. This is accessed by casting the value returned by the 'Type' method.<br /><br />The methods for accessing the fields of a 'StructType' do not return a 'Value', but a 'StructField', a struct that contains data about the field, including what we are looking for: the field's name. As such, we iterate through it much as we would the 'StructValue''s fields. <br /><br /><span style="font-family:courier new;">func printAny (val reflect.Value) {<br /> switch v := val.(type) {<br /> case *reflect.PtrValue:<br /> if v.IsNil () {<br /> fmt.Println ("nil")<br /> }<br /> printAny (v.Elem ())<br /> case *reflect.StructValue:<br /> typ := v.Type ().(*reflect.StructType);<br /><br /> for i := 0; i < typ.NumField (); i++ {<br /> name := typ.Field (i).Name;<br /> field := v.FieldByName (name);<br /><br /> fmt.Printf ("%s: ", name);<br /> printAny (field)<br /> }<br /> case *reflect.IntValue:<br /> fmt.Printf ("%d\n", v.Get ())<br /> case *reflect.StringValue:<br /> fmt.Println (v.Get ())<br /> case *reflect.BoolValue:<br /> fmt.Printf ("%t\n", v.Get ())<br /> default:<br /> fmt.Println ("Unknown Type")<br /> }<br /></span><p><span style="font-family:courier new;">}</span></p><p>And that's it! Try it out with our 'Stuff' struct:<br /></p><br /><span style="font-family:courier new;">func main () {<br /> a := Stuff{4, "Hi!", true};<br /> PrintAny (&a)<br />}</span><br /><span ><br /></span>The obvious application for a similar function would be serialization, though I would not use it for complex structures. It would indeed be best only for small structures tailor made to save only that which needs to be saved. Everything else can be derived when reading from the saved data.<br /><br />Another application is the ... parameter, as I mentioned at the beginning of this article. The ... parameter is treated as a struct containing the values passed into it. For example:<br /><br /><span style="font-family:courier new;">fmt.Printf (format, 1, 2.3, true, "me");</span><br /><br />The types that Printf deals with internally are actually a string and a struct with an int field, a float field, a bool field, and a string field. Of course, it also handles more types that my little example does, but it is not difficult to implement them.Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com4tag:blogger.com,1999:blog-6913352122658298052.post-73440864356285310472009-11-14T17:47:00.000-08:002009-11-14T19:03:31.296-08:00Generator functions in Go<p>When I learned how channels work in Google's Go language, one of the first thoughts that came to my mind was not inter-thread communication, but generator functions ala Python's yield statement. That is because of the Wikipedia article on the subject, which mentions that Java can implement generators via threading. Common threading, however, is not always a quick and easy process, so I more-of-less decided that the feature could only really work well in languages that explicitly have the feature. That is not the case with Go.</p><p>Goroutines are a light-weight implementation of threading, without much of the complexity associated with threading. All you need to launch a goroutine is any function and the 'go' keyword. Channels can help for passing data out of goroutines and when channels are created without defining a buffer size, they block execution until the channel is read from. That feature of channels is very similar to what Python's 'yield' statement does.</p><p><span style="font-family:courier new;">func Count (start, length int) chan int {<br /> yield := make (chan int);<br /><br /> go func () {<br /> for num := start; num < start + length; num++ {<br /> yield <- num<br /> }<br /><br /> close (yield)<br /> } ();<br /><br /> return yield<br />}</span><br /></p><p>As you can see, it's slightly different from Python, but very workable and without much difficulty. The actual code for the generator is held within an anonymous function, but outside of that all we do is create the channel and return it.</p><p>Note that the channel is closed at the end of the generator. This is important, as trying to read beyond the end of the goroutine causes the program to panic and die. If, on the other hand, the channel is closed and one reads beyond the end of the goroutine, the result is simply zeros.</p><p>Another great feature of channels is that they are one of the types that may be used by the 'range' clause in 'for' loops. Thus, in such a loop one does not have to check to see if the channel is closed; Go does that for you.</p>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com0tag:blogger.com,1999:blog-6913352122658298052.post-55775548513806916392009-11-11T20:32:00.000-08:002009-11-11T20:33:44.072-08:00One day holiday, but no Dragon AgeI made the error of letting Impulse patch Dragon Age and the game doesn't work any more. I'm certainly not going to re-download the thing, I'm hoping that System Restore might solve things. . . If not, then it's the weekend before I play it again.<br /><br />Instead I spent the day playing around with Google's new 'Go' programming language. I really like it! It's got many great modern features and certain elements of the syntax remind me of Pascal. Most important, to me, are the features that allow one to make the most of multi-core systems. Python, which I've been playing with most in recent times, is actually best on single-core systems, unfortunately. I just might find myself migrating toward Go. . .<br /><br />The make-or-break point of it, though, will be its ability to interface with existing C libraries. Right now that's a bit iffy. I'm trying to write an interface to a library I've been using lately and it inexplicably refuses to work with some functions. Fortunately, the compiler is open-sourced and not particularly huge, so perhaps I can figure out what's happening. . . That might have to wait for the weekend, too.Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com0tag:blogger.com,1999:blog-6913352122658298052.post-21917037297203060422009-10-24T06:21:00.001-07:002009-12-08T08:03:48.293-08:00Fast Rendering With libtcod in Python<p><span style="color:#000000;">Python, being an interpreted language, is not all that speedy. Obviously a great deal of effort has gone into optimisation of the interpreter, but by far the best way of producing fast code is via the liberal use of functionality implemented in C. By this I do not mean that one should go out of their way to write one's own C extensions for every taxing operation. It is usually sufficient to make use of existing libraries, both standard and extension.</span></p><p><span style="color:#000000;">The Chronicles of Doryen Library, or libtcod, is an ASCII rendering engine, primarily intended for rogue-like games. It features full 24-bit colour and a very nice set of utility modules -- basically everything one might need to produce a rogue-like. As I said, though, it is a </span><em><span style="color:#000000;">rendering</span></em><span style="color:#000000;"> engine and not a </span><em><span style="color:#000000;">game</span></em><span style="color:#000000;"> engine. One still has to implement one's own data structures and game loop.</span></p><p><span style="color:#000000;">The most obvious way of printing characters on screen in libtcod is via the put_char function. It places a character at the specified location in a buffer. The character's colour may be set either by previously altering the default foreground and background colours (via set_background_color and set_foreground_color) or by afterward setting the colours for that particular location on screen (via set_back and set_fore). The problem here is obvious, as what you have is a minimum of three function calls for each and every character on screen. If one is rendering to a traditional 80 by 25 viewport, that is two-thousand characters or </span><em><span style="color:#000000;">six</span></em><span style="color:#000000;">-thousand function calls every frame. That is not including whatever happens throughout the rest of the program loop.</span></p><p><span style="color:#000000;">Clearly another method is required. Fortunately, libtcod provides functions capable of printing multiple characters (ie: a string) with a single call: print_left, print_center, and print_right. Furthermore, it provides functionality though which one may specify colours within the string. This is how I implemented my solution.</span></p><p><span style="color:#000000;">First off, let us start with a data structure:</span></p><p><span style="font-family:courier new;">class Cell (object):<span style="color:#000000;"><br /></span> __slots__ = '_fg', '_bg', 'char'<span style="color:#000000;"><br /></span><span style="color:#000000;"></span><span style="color:#000000;"><br /></span> def __init__ (self, fg, bg, char):<span style="color:#000000;"><br /></span> self.fg = fg<span style="color:#000000;"><br /></span> self.bg = bg<span style="color:#000000;"><br /></span><span style="color:#000000;"> self.char = char</span></span><span style="font-family:courier new;"><span style="color:#000000;"><br /></span></span></p><p><span style="color:#000000;">To be honest, using a class is somewhat slower than simply storing this data in a tuple, but this makes the code more readable. I used __slots__ because it does at least provide a small boost in speed.</span></p><p><span style="color:#000000;">The easiest way to store the scene is in a list. More specifically in a list of lists. The outer list is a collection of rows, with each inner list being the rows themselves. Let us generate a random scene:</span></p><p><span style="color:#000000;"> </span><span style="font-family:courier new;">chars = ['\'', '`', ',', '.', '.', '.']<span style="color:#000000;"><br /></span><span style="color:#000000;"> raw_scene = [[Cell ((1, 255, 1), (1, 1, 1), random.choice (chars)) for x in range (width)] for y in range (height)]</span></span><span style="color:#000000;"></span><span style="color:#000000;"><br /></span></p><p><span style="color:#000000;">There: a Dwarf Fortress-like grassy field!</span></p><p><span style="color:#000000;">If none of that code makes sense to you, I suggest that you study </span><a href="http://docs.python.org/tutorial/classes.html#generator-expressions"><span style="color:#000000;">Generator Expressions</span></a><span style="color:#000000;">. They are immensely useful.</span></p><p><span style="color:#000000;">Anyway, this is the raw data from which we will construct the scene. We keep it in memory for cases where we must update the scene, as the compiled data may not be as intuitive to alter (though it is certainly possible).</span></p><p><span style="color:#000000;">The scene is compiled by converting every cell into a string consisting of libtcod colour codes and the cell's character:</span></p><p><span style="font-family:courier new;">def compile_scene (raw_scene):<span style="color:#000000;"><br /></span> scene = []<span style="color:#000000;"><br /></span><span style="color:#000000;"></span><span style="color:#000000;"><br /></span> for y in range (height):<span style="color:#000000;"><br /></span> scene.append ([])<span style="color:#000000;"><br /></span> <span style="color:#000000;"><br /></span> for x in range (width):<span style="color:#000000;"><br /></span> cell = raw_scene[y][x]<span style="color:#000000;"><br /></span> scene[y].append ('%c%c%c%c%c%c%c%c%c%c' % ((tcod.COLCTRL_FORE_RGB, ) + cell.fg + (tcod.COLCTRL_BACK_RGB, ) + cell.bg + (cell.char, tcod.COLCTRL_STOP)))<span style="color:#000000;"><br /></span><span style="color:#000000;"></span><span style="color:#000000;"><br /></span><span style="color:#000000;"> return scene</span></span><span style="font-family:courier new;"><span style="color:#000000;"></span><span style="color:#000000;"><br /></span></span></p><p><span style="color:#000000;">Leaving the individual little strings separate from each other allows one to later swap it with a different one. Besides, Python provides the functionality to quickly combine them when we draw the scene.</span></p><p><span style="color:#000000;">Drawing the scene is simply a matter of using the join function of Python strings to combine the strings in every row. We could technically also add a newline character to the end of every row and then combine the rows, allowing one to draw the entire scene in a single function call, but for some reason that produced a strange bug for me whereby sometimes the scene would not fully render. I even ported the program to C and encountered the same issue. Printing each line one-by-one seems to work, though, and it is not much slower.</span></p><p><span style="font-family:courier new;">def draw (con, scene):<span style="color:#000000;"><br /></span> scene_str = [''.join (scene[y]) for y in range (height)]<span style="color:#000000;"><br /></span><span style="color:#000000;"></span><span style="color:#000000;"><br /></span> for y in range (height):<span style="color:#000000;"><br /></span><span style="color:#000000;"> tcod.console_print_left (con, 0, y, tcod.BKGND_SET, scene_str[y])</span></span><span style="color:#000000;"></span><span style="color:#000000;"><br /></span></p><p><span style="color:#000000;">We can even go further and draw only a portion of the scene:</span></p><p><span style="font-family:courier new;">def draw (con, scene, left, top):<span style="color:#000000;"><br /></span> scene_str = [''.join (scene[y][left:left + scr_width]) for y in range (top, top + scr_height)]<span style="color:#000000;"><br /></span><span style="color:#000000;"></span><span style="color:#000000;"><br /></span> for y in range (scr_height):<span style="color:#000000;"><br /></span><span style="color:#000000;"> tcod.console_print_left (con, 0, y, tcod.BKGND_SET, scene_str[y])</span></span><span style="color:#000000;"></span><span style="color:#000000;"><br /></span></p><p><span style="color:#000000;">This is useful in cases where the scene encompasses an area larger than the viewport.</span></p><p><span style="color:#000000;">The full version of my test program also incorporates an update function and several light sources altering the visibility of each cell. It is in that version that the bug I mentioned appeared.</span></p><p><span style="color:#000000;">Anyway, I hope this helps anyone who has had problems with rendering speed in Python. It has been a long time since I wrote an article on my blog, so at the very least it was worthwhile for me. . .</span></p>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com1tag:blogger.com,1999:blog-6913352122658298052.post-32083541578330503092009-06-23T18:43:00.000-07:002009-06-23T19:25:31.049-07:00The Mote in God's Eye<p>I do not think that one who basks in political correctness should bother with <strong>The Mote in God's Eye</strong>, by Larry Niven and Jerry <span class="blsp-spelling-error" id="SPELLING_ERROR_0">Pournelle</span>. If one looks both closely and shallowly at this book, one might decide that one has found trove of male chauvinism and racism. I tend to do so, though only for my own personal entertainment.</p><p>The imperial navy, for example, seems to be comprised entirely of men. This is not unusual, historically or currently, but the great assumption is often that the future will hold greater equality in all things. Another example here is that the purpose of aristocratic women is apparently to perform as social butterflies, get married, and pop out heirs. Once again, equality is generally expected in future settings, but then again: who is to say how the future and future human attitudes will develop? The assumption of equality is based on current conditions facing no drastic changes -- which is entirely naive. (There is another example, but it's a spoiler, so I won't reveal it.)</p><p>As for racism, the <span class="blsp-spelling-error" id="SPELLING_ERROR_1">Moties</span> (the alien race described) are a species with several genetic castes somewhat akin to polymorphism in insects. There is a master caste, a mediator caste, a medical caste, a warrior caste, an engineer caste, etc. Key in the argument of racism is that the master caste is white and the engineer caste (<span class="blsp-spelling-error" id="SPELLING_ERROR_2">intrinsicly</span> gifted in making things, but incapable of higher thought processes) is brown. Here I can say that dark and light are used as the easily recognisable <span class="blsp-spelling-error" id="SPELLING_ERROR_3">archetyes</span> that they are, in western culture. If that's not clear enough, think of the terms "white-collar" and "blue-collar".</p><p>Enough of the self-indulgent under-thinking, though. <strong>Mote</strong> is basically a story of first contact -- the first first-contact -- with an intelligent alien civilisation. Most books that I've read that deal with such a scenario assume a human civilisation that has yet to explore and colonise beyond the solar system -- assuming they got far off Earth at all. Basically: contemporary settings. In <strong>Mote</strong>, humanity has gone through the cycles of multi-stellar civilisation twice (the <span class="blsp-spelling-error" id="SPELLING_ERROR_4">CoDominion</span> and the First Empire), each followed by a collapse and period of barbarism, and has once again risen to a vast Empire. For me, this is a unique experience.</p><p>The book is presented largely as a political drama, with several mysteries involving characters motivations. There is little physical action, though what there is gripped my eyes and I had little desire to pull away. All-in-all it had a somewhat <span class="blsp-spelling-error" id="SPELLING_ERROR_5">Asimovian</span> feel. If you've read Isaac <span class="blsp-spelling-error" id="SPELLING_ERROR_6">Asimov's</span> <strong>Foundation</strong> series, you'll know what I mean. Dramatic irony and discovery are where most of the action is, and I think <span class="blsp-spelling-error" id="SPELLING_ERROR_7">Pournelle</span> and Niven did a great job.</p><p>To be honest, though, I do have a couple gripes. First is due to my own misconceptions: I expected more military science fiction; an interstellar war. I didn't get that, but I probably should have read the synopsis more closely. I don't like to do that, though, as it may spoil too much. The second is related to the romance in the novel. The pairing is far too obvious and it develops far to quickly and suddenly. I have this problem with a great many books by a great many authors, though, so it shouldn't be surprising, anymore.</p><p>As I said, though, it's overall a great book. Probably because it doesn't involve war and high military drama, it may be one of the best first-contact stories out there. Definitely a recommended read to all interested in such things.</p>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com0tag:blogger.com,1999:blog-6913352122658298052.post-19726582587287067302009-06-20T22:40:00.000-07:002009-06-20T22:41:27.885-07:00Acceleration/DecellerationSay we want to move an object to a particular point in the shortest amount of time, given a maximum acceleration. It follows that the object must accelerate constantly until it comes to a point where it must decellerate constantly in order to come to a stop at the destination. Looking at this problem we have a known starting velocity, a known final velocity, a known total distance, and a known acceleration. There is a kinematics equation that uses all of those values:<br /><br /><span style="font-family:courier new;">v**2 = v0**2 + 2 * a * d</span><br /><br />Unfortunately, that's only one acceleration, but our problem actually consists of two parts: an acceleration and a decelleration. At the end of the object's acceleration it reaches a maximum velocity, the final velocity for that part. The maximum velocity then becomes the starting velocity for the second part. Therefore we have two equations:<br /><br /><span style="font-family:courier new;">v_max**2 = v0**2 + 2 * a * d1<br />vf**2 = v_max**2 + 2 * -a * d2</span><br /><br />This leads to two more unknowns: d1 and d2, the distances travelled during the first and second parts, respectively. However, the total of d1 and d2 is known as the distance from the start to the destination. Therefore, if we solve for d1 and d2 and add the results, it should equal the total distance.<br /><br /><span style="font-family:courier new;">d1 = (v_max**2 - v0**2) / (2 * a)<br />d2 = (vf**2 - v_max**2) / (2 * -a)<br />d = d1 + d2</span><br /><br />The maximum velocity is still unknown, though, so let's sub in the formulas for d1 and d2:<br /><br /><span style="font-family:courier new;">d = (v_max**2 - v0**2) / (2 * a) + (vf**2 - v_max**2) / (2 * -a)</span><br /><br />... simply it:<br /> <br /><span style="font-family:courier new;">d = (2 * v_max**2 - v0**2 - vf**2) / (2 * a)</span><br /><br />... and solve for the maximum velocity:<br /><br /><span style="font-family:courier new;">v_max = sqrt ((2.0 * a * d + v0**2 + vf**2) / 2.0)</span><br /><br />Now, we simply have the object accelerate to that velocity and then decellerate back down to the final velocity. In the end, the object should be at the destination. Of course, now that the maximum velocity is a known value, one can now calculate d1 and use that value to determine how long the object should accelerate.Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com0tag:blogger.com,1999:blog-6913352122658298052.post-83603558210631836542009-06-14T10:30:00.001-07:002009-06-22T04:48:40.088-07:00King David's Spaceship<p>I just finished reading <strong>King David's Spaceship</strong>, by Jerry Pournelle. It's part of his Future History series, though very far removed from the Codominion era books. Those books ended with a prequel to a galactic empire, though the empire itself is never touched upon except as a history to later books. This one takes place after that empire's fall and the during the rise of a new one.</p><p>Anyway, for a title that indicates a plot about building a spaceship, the story itself has little to do with that. It is the ultimate goal, but the bulk of the plot takes place in a medieval environment. That's not to say that I am disappointed, though. Pournelle writes plenty of military science fiction and he's good at it, even when the 'military' part is with early medieval technology. No, instead of disappointed I was merely surprised at where the focus ended up.</p>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com0tag:blogger.com,1999:blog-6913352122658298052.post-35480455100827377012009-06-13T10:55:00.000-07:002009-06-13T10:56:58.140-07:00CyborgJust finished watching<strong> Cyborg</strong>, a Jean-Claude Van Damme film from 1989. When I was young I remember Super Channel (a pay movie channel, back then) occasionally had promotions whereby they provided free viewing for a week. Those were the only times I ever saw anything from that channel. Once in a while, my sister would set her alarm clock to an early morning hour and wake me up so we could watch a late movie that looked interesting. That's how I first saw this film.<br /><br />I really enjoyed it back then, having never before seen anything like the post-apocalyptic vision presented. It had good action, with a particularily menacing villain, and an element of drama that made it yet more memorable. Watching it again, I recognise the old, cheap effects (by modern standards), and the generally bad acting (not just from Van Damme). I can still enjoy it, though, and perhaps not all of that is simply due to nostalgia.<br /><br />On another note, the movie reminds me alot of <strong>Fallout</strong>. :) The world presented is more lush outside of urban areas, but the ruined cities and the scavenged look of the costuming is definitely <strong>Fallout</strong>-like.Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com0tag:blogger.com,1999:blog-6913352122658298052.post-34332425541001226352009-06-10T10:53:00.000-07:002009-06-10T12:33:01.577-07:00Collision Detection for Fast Objects and Circle-Line Intersection<p>In my current project I produced my own little set of classes for simulating physics. It's very unrealistic, at this point, because realistic physics makes it very difficult to implement a thrust control AI. More on that another time. For now, I'm talking collision detection.</p><p>The objects I'm dealing with are very small relative to the velocities at which they may travel. These are spacecraft and projectiles moving at realistic speeds -- not like one would see in a game like Star Control or indeed most other space sims, where craft seem to move slower than modern aircraft do. In my program, projectiles like missiles are often moving so fast that simply collision detection allows them to pass right through their targets. That's a problem.</p><p>The easiest solution to this is to simply use a smaller timestep. I've locked the framerate at only 25 Hz, but I step through the physics update functions four times per frame. As far as the physics is concerned, the actual framerate is 100 Hz. Even with such a framerate, collisions often fail to register. The solution I decided upon was to implement a second step to collision detection whereby the system would also look at the area between the object's current position and its previous position.</p><p>The basic collision detection simply uses circles. I detect collisions between the circular collision hulls of the current and previous position by defining a rectangle between them whose side lie tangent to both circles. The slope of those tangent lines is no chore to discover as the radius of each circle is the same. The slope is simply the slope of the vector that connects their centres:</p><p><span style="font-family:courier new;"># get the positions<br />x0, y0 = pos<br />x0p, y0p = prev_pos<br /><br /># get the distance between the two<br />dx, dy = x0 - x0p, y0 - y0p<br />dist = math.hypot (dx, dy)<br /><br /># normalize the vector<br />ndx, ndy = dx / dist, dy / dist<br /><br />slope = ndy / ndx</span></p><p><span style="font-family:georgia;">We will use the normalized vector to determine where the corners of the rectangle lie. This is found simply by rotating the vector 90 degrees left and right. Multiply the results by the radius of the circles to produce vectors and add them to the current and previous positions to get the corners.</span></p><p><span style="font-family:courier new;"># get the end-piece slopes<br />ex0, ey0 = -ndy, ndx<br />ex1, ey1 = ndy, -ndx<br /><br /># get the corners of the rectangle<br />px0, py0 = x0p + ex0 * radius, y0p + ey0 * radius<br />px1, py1 = x0 + ex0 * radius, y0 + ey0 * radius<br />px2, py2 = x0 + ex1 * radius, y0 + ey1 * radius<br />px3, py3 = x0p + ex1 * radius, y0p + ey1 * radius<br /><br /></span><span style="font-family:georgia;">Assuming that the previous position (x0p, y0p) is to the left of the current position (x0, y0), the top-left point is (px0, py0). The rest of the points continue clockwise around the rectangle.</span><span style="font-family:courier new;"><br /></span></p><p><span style="font-family:georgia;">What we now need to do is test for a collision between the rectangle and the circular collision hull of the other object. Cirlce-Rectangle collision occurs when either the circle touches a rectangle edge or when the centre of the circle falls with the bounds of the rectangle. The latter is easier to test for, of course.</span></p><p><span style="font-family:georgia;">Determining whether a point is within a rectangle is simply a matter of finding which side of each edge the point lies. Simply:</span><span style="font-family:courier new;"> </span><span style="font-family:courier new;"> </span><span style="font-family:courier new;"> </span><span style="font-family:courier new;"> </span><span style="font-family:courier new;"> </span><span style="font-family:courier new;"> </span><span style="font-family:courier new;"> </span><span style="font-family:courier new;"> </span><span style="font-family:courier new;"> </span><span style="font-family:courier new;"> </span><span style="font-family:courier new;"> </span></p><p><span style="font-family:courier new;">def get_side (p0, p1, point):<br /> x, y = point<br /> x0, y0 = p0<br /> x1, y1 = p1<br /> <br /> ex0 = x1 - x0<br /> ey0 = y1 - y0<br /> <br /> ex1 = x - x1<br /> ey1 = y - y1<br /> <br /> return ex0 * ey1 - ey0 * ex1</span></p><p><span style="font-family:georgia;">The order in which points are entered into this function is important. Entered clockwise: if the return value is positive, the point lies above the line; if the value is zero, the point lies on the line; if the value is negative, the point lies below the line. Therefore the point lies within the rectangle if the return value is negative for all sides.</span></p><p><span style="font-family:georgia;">If the centre of the circle is not within the rectangle, it is still possible that it touches one of the edges. The only two edges we have to test are the top and bottom edges. The end-pieces lie within the circles of the current and previous position circles, so we need not test them.</span></p><p><span style="font-family:georgia;">I must admit that I had great difficult trying to find an algorithm for Circle-Line Intersection. I found a few sources where simply code was given, but I prefer an explanation to accompany code. Eventually it dawned upon me to simply use the equations for lines and circles:</span></p><p><span style="font-family:courier new;"># line<br />y = m * x + b<br /><br /># circle<br />r**2 = (x + x0)**2 + (y + y0)**2</span></p><p><span style="font-family:georgia;">The circle equation is easiest to deal with if simplified to assume that its origin is (0, 0). Therefore:</span></p><p><span style="font-family:courier new;">r**2 = x**2 + y**2</span></p><p><span style="font-family:georgia;">If we do that, however, we must account for that in the for the line equation. The easiest way to do that is to simply subtract the origin coordinates from the coordinates of the current and previous positions.</span></p><p><span style="font-family:georgia;">For the line equation, we found the slope, m, previously, and can find b by substituting either the current or previous position coordinates (modified as in the previous paragraph) into x and y. Solving for b:</span></p><p><span style="font-family:courier new;">b = y0 - m * x0</span></p><p><span style="font-family:georgia;">Now, let us take the original line equation and substitute it for y in the circle equation:</span></p><p><span style="font-family:courier new;">r**2 = x**2 + (m * x + b)**2</span></p><p><span style="font-family:georgia;">Before we try to solve for x, let's evaluate the equation as far as it can go:</span></p><p><span style="font-family:courier new;">r**2 = x**2 + m**2 * x**2 + m * x * b + m * b + b**2</span></p><p><span style="font-family:georgia;">It looks intimidating, but we can turn it into a quadratic equation:</span></p><p><span style="font-family:courier new;">0 = (1 + m**2) * x**2 + m * x * b + m * b + b**2 - r**2</span></p><p><span style="font-family:georgia;">We can then solve for x via the quadratic formula, but to be honest we don't actually need it. As it turns out, all we need is the result of the discriminant:</span></p><p><span style="font-family:courier new;">D = b**2 - 4 * a * c</span></p><p><span style="font-family:georgia;">The discriminant, after all, exists within the quadratic formula's square-root, which will not result in a real number if the discriminant is negative. Ultimately, what this means is that the circle does not intersect the line if the discriminant is negative. If it is not negative, the circle intersects the line at one or two points.</span></p><p><span style="font-family:georgia;">The expressions a, b, and c are extracted from our quadratic equation as follows:</span></p><p><span style="font-family:courier new;">a = 1 + m**2</span></p><p><span style="font-family:courier new;">b = m * b</span></p><p><span style="font-family:courier new;">c = m * b + b**2 - r**2</span></p><p><span style="font-family:georgia;">The resulting discriminant is:</span></p><p><span style="font-family:courier new;">D = m**2 * b**2 - 4 * (1 + m**2) * (m * b + b**2 - r**2)</span></p><p><span style="font-family:georgia;">There are no unknown values in this equation. We have m, the slope, r, the radius, and b. Here's the final function for Circle-Line Intersection:</span></p><p><span style="font-family:courier new;">def circle_line_intersection (p0, p1, origin, radius):<br /> x, y = origin<br /> <br /> px0, py0 = p0[0] - x, p0[1] - y<br /> px1, py1 = p1[0] - x, p1[1] - y<br /> <br /> dx, dy = px1 - px0, py1 - py0<br /> <br /> if dx == 0.0:<br /> return radius > abs (px0)<br /> <br /> m = dy / dx<br /> b = py0 - m * px0<br /> <br /> return m**2 * b**2 - 4 * (1 + m**2) * (m * b + b**2 - radius**2) >= 0.0<br /><br /></span><span style="font-family:georgia;">I test if dx is equal to zero because if it is, we'll end up with a division-by-zero error. However, all that means is that the line is vertical. As such, we can simply test one of the positions' x-coordinates against the radius of the circle.<br /></span></p><p><span style="font-family:georgia;">This form of collision detection will not tell you exactly where the collision occured, of course. However, that was not relevant to my needs, so I gratefully never considered it. All I needed to know was whether my projectile had hit something or not, and this works quite well.</span></p><p><span style="font-family:georgia;">There are some problems with this solution, of course. For example, if the projectile is moving along a curved path, this does not provide a perfect solution, as a rectangle has entirely flat sides. Right now, however, I don't particularily feel like looking into collisions with arbitrary curves. . .</span></p><p><span style="font-family:courier new;"> </span></p>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com1tag:blogger.com,1999:blog-6913352122658298052.post-75853629245166403132009-06-09T07:06:00.000-07:002009-06-09T08:04:47.744-07:00Circular number systems<p>When one deals with angles one must eventually find a way to work around the barrier between 359 degrees and 0 degrees. For example, if one has an angle at 5 degrees and another at 355 degrees, what is the distance between them? If one subtracts normally the result will be either 350 or -350, depending on the order one places them in the expression. This is mathematically correct, producing the difference, but rarely is that what one wants.</p><p>The general case is finding out how to rotate an object to a particular destination. Ideally one should rotate the object such that the shortest amount of time is taken, which means taking the shortest distance. Rotating 350 degrees is obviously, to human perception, not the shortest distance. The shortest distance is -10 degrees, of course, but the problem is how to write a program to give that result.</p><p>It is easy, if one uses a couple 'if-else' statements. We start at 5 degrees and need to get to 355, so try the basic equation:</p><p><span style="font-family:courier new;">distance = destination - origin</span></p><p><span style="font-family:courier new;">distance = 355 - 5</span></p><p><span style="font-family:courier new;">350</span></p><p><span style="font-family:georgia;">This is, as mentioned earlier not the answer we want, so subtract maximum span of angle values, 360, and we have our answer: -10. This works as long as the distance crosses over zero and the basic equation results in a positive number. If it results in a negative number, then we add 360 instead. If we are not crossing over zero, we add or subtract nothing. One can always tell if the distance crosses over zero if the result of the basic equation is outside of the range (-180, 180).</span></p><p><span style="font-family:georgia;">Let's turn this into Python code:</span></p><p><span style="font-family:courier new;">def diff (start, end):<br /> dist = end - start<br /> <br /> if dist < -180:<br /> dist += 360<br /> if dist > 180:<br /> dist -= 360<br /> <br /> return dist</span></p><p><span style="font-family:georgia;">Simple enough and it works to a degree even when the values are not clamped to (0, 360]. However, I said 'to a degree'. If the starting angle is 721 and the end is -1, the distance, according to this function is -362. 721 degrees is actually just 1 degree, so the distance should be -2. To solve for this we should convert all values such that they appear between the standard range of (0, 360]. Therefore the new function is:</span></p><p><span style="font-family:courier new;">def diff (start, end):<br /> start = start - int (start / 360) * 360<br /> end = end - int (end / 360) * 360<br /> <br /> dist = end - start<br /> <br /> if dist < -180:<br /> dist += 360<br /> if dist > 180:<br /> dist -= 360<br /> <br /> return dist</span></p><p><span style="font-family:georgia;">This works, perfectly, but it's a rather long function. For a time I was satisfied with it, but thought that a shorter way was possible. I presented my problem and solution on the PyGame newsgroup and was greeted with some much better solutions. Here's one:</span></p><p><span style="font-family:courier new;">def diff (start, end):<br /> return (end - start + 180) % 360 - 180<br /><br /></span><span style="font-family:georgia;">I started with a function with an 8-line body of code (not counting whitespace) and got back a function with a single line of code. There's no conditional statements, either. It is simply perfect.<br /></span></p><p><span style="font-family:georgia;">This function is easily modified to work with whatever range of values one chooses. If one works with radians instead of degrees:</span></p><p><span style="font-family:courier new;">def diff (start, end):<br /> return (end - start + 0.5 * pi) % pi - 0.5 * pi</span><span style="font-family:courier new;"><br /></span></p><p>Or how about a twelve-hour clock?</p><p><span style="font-family:courier new;">def diff (start, end):<br /> return (end - start + 6) % 12 - 6</span></p><p><span style="font-family:georgia;">Perfect!</span></p>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com1tag:blogger.com,1999:blog-6913352122658298052.post-57028455609474011002009-05-31T19:24:00.000-07:002009-06-09T07:06:10.534-07:00A belated introduction. . .<p>I registered this blog some weeks ago, but between my ISP and some strange Windows 7 network bugs, I suffered enough annoying internet outages at the time that I never got around to producing my first post. Well, here it is -- not the post I had originally written, but a post nevertheless.</p><p>This is Cheesesun Works! What is Cheesesun? Cheesesun is what I am told my handle, Ostsol, means if translated to English from Swedish. That wasn't what I had in mind when I originally chose my handle, but I like it.</p><p>Cheesesun Works will primarily be my development blog. Programming is like doodling, to me. I may not produce much in terms of finished products, but I do like to experiment and learn. Hopefully I will eventually finish something, but until then, here I will post my development thoughts and discoveries.</p><p>While secondary, I'll also likely use this as a log of my readings. I use public transit every working day (no car; I got my learner's permit only recently) and work on the opposite side of the city from where I live. The result is a 45 minute span each way in which I have nothing to do. So I read.</p>Ostsolhttp://www.blogger.com/profile/17832423842597481746noreply@blogger.com0