intfiction.org

The Interactive Fiction Community Forum
It is currently Mon Sep 24, 2018 5:33 am

All times are UTC - 6 hours [ DST ]




Post new topic Reply to topic  [ 21 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
PostPosted: Sat Sep 15, 2018 4:34 pm 
Online
User avatar

Joined: Sun Nov 22, 2009 12:58 pm
Posts: 776
Location: Malmö, Sweden
zarf's hunch was right: it was something else. In this case, the algorithm used relied on sorting. I've settled instead for doing a quick box-pass: determine a box that would fit the radius, reject any x coordinate that doesn't fit in it, otherwise reject y-coordinate, and finally doing the expensive square root for the remaining candidates. I thought I might have to do a Newton-Raphson variation if the idea didn't pan out (had all sorts of ideas on how to guesstimate the value, one being a list of precomputed square-root values in a table), but as it turned out none of that needed to be done.

Anyway, much obliged to you guys for your insight. Some cool ideas in this thread.

_________________
~Björn Paulsen


Top
 Profile Send private message  
Reply with quote  
PostPosted: Sun Sep 16, 2018 10:31 am 
Offline
User avatar

Joined: Mon Aug 28, 2017 12:07 pm
Posts: 42
Eleas wrote:
I've settled instead for doing a quick box-pass: determine a box that would fit the radius, reject any x coordinate that doesn't fit in it, otherwise reject y-coordinate, and finally doing the expensive square root for the remaining candidates.


Can you explain what you are actually trying to calculate? From the clues, it sounds like you are trying to determine whether something is contained within a circle? Or are you looking for the as the crow flies distance? Or something else?

There are two very old computer graphics algorithms that rely only on addition and subtraction to draw circles and line segments. I think they might be fairly easy to modify to estimate whether something is inside or outside a circle or estimate distance between two point. They won't be precise to the decimal point as it is integer math only, but it might be good enough for the problem you want to solve. Doing the boxing first would still be a good idea.

See:

https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

Also, as an aside, wondering whether the midpoint circle algorithm could be modified to provide trigonometry functions? Although not sure anyone needs/wants that in their interactive fiction?

_________________
"She is not refined. She is not unrefined. She keeps a parrot."


Top
 Profile Send private message  
Reply with quote  
PostPosted: Sun Sep 16, 2018 4:48 pm 
Online
User avatar

Joined: Sun Nov 22, 2009 12:58 pm
Posts: 776
Location: Malmö, Sweden
Code:
Can you explain what you are actually trying to calculate? From the clues, it sounds like you are trying to determine whether something is contained within a circle? Or are you looking for the as the crow flies distance? Or something else?


Basically, I have a 2D field with a bunch of coordinate points ("destinations"), and the player will be able to go a certain distance along that grid, always point to point. The function I was referring to earlier would return a list of all viable destinations. It made several unclever assumptions and managed to make the lookup of 256 destinations slow enough to be noticeable. My new one ditched the contortions and the overhead as well.

Those are cool links though. This wouldn't be a good use of them, I think (we're only concerned with endpoints here, as opposed to line or circumference shape), but I can think of a few projects that might use a fast line-draw algorithm or two. :)

_________________
~Björn Paulsen


Top
 Profile Send private message  
Reply with quote  
PostPosted: Sun Sep 16, 2018 5:07 pm 
Offline

Joined: Tue Mar 09, 2010 2:34 pm
Posts: 5360
Location: Burlington, VT
I tried to use trigonometry in IF once! I had got a lot of pirate-related songs for Shufflecomp 2 and for some reason I decided both this would be a good time to start on that Strange Adventures in Infinite Space-like I've always wanted to do, and that the first thing to start with would be the sailing mechanics including a bunch of stuff about the trigonometry of tacking. Needless to say my Shufflecomp 2 entry never got made, but I did discover a bug in the trig functions (which makes me think no one else has ever actually used them).

Eleas, if the thing is that the player can go a certain distance point-to-point on the grid, won't it be enough to check whether the square of the difference in x coordinates plus the square of the difference in the y coordinates is less than or equal to the square of the maximum allowable distance? Then you could do it all in cheap integer arithmetic.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Sun Sep 16, 2018 7:32 pm 
Offline
User avatar

Joined: Mon Aug 28, 2017 12:07 pm
Posts: 42
Glad you have a solution that works for you. I haven't thought about those algorithms since I used to dabble with 6502 assembly language a very long time ago. Thanks for triggering the nostalgia

I don't know Inform7 real well, but it seems to me that maybe instead of using a table to store this data, this is a job for a data graph, a.k.a relations. I'm not comfortable enough with Inform to figure out how to write that, but it seems like that relations might be a good fit for linking teleportation pads together?

Been trying to improve my comp sci skills lately and have been studying a (very) little graph theory. There is a concept where the line (edge, link,relation, whatever you want to call it) has a weight value associated with it so that you can calculate the shortest distance between two nodes. For example consider cities linked by highways. What is the shortest path between two cities? That's different than fewest hops between cities. You have to take into account how long the roads are. Question: Does Inform7 have the ability to weight the relations between things? What would that code look like?

_________________
"She is not refined. She is not unrefined. She keeps a parrot."


Top
 Profile Send private message  
Reply with quote  
PostPosted: Sun Sep 16, 2018 7:45 pm 
Offline
User avatar

Joined: Mon Aug 28, 2017 12:07 pm
Posts: 42
matt w wrote:
Sailing mechanics including a bunch of stuff about the trigonometry of tacking.


I can see that. Also, charting a course with a sextant. It wouldn't be a game I could play though. I can barely handle compass directions. :oops:

_________________
"She is not refined. She is not unrefined. She keeps a parrot."


Top
 Profile Send private message  
Reply with quote  
PostPosted: Mon Sep 17, 2018 1:51 am 
Online
User avatar

Joined: Sun Nov 22, 2009 12:58 pm
Posts: 776
Location: Malmö, Sweden
matt w wrote:
Eleas, if the thing is that the player can go a certain distance point-to-point on the grid, won't it be enough to check whether the square of the difference in x coordinates plus the square of the difference in the y coordinates is less than or equal to the square of the maximum allowable distance? Then you could do it all in cheap integer arithmetic.


I'm sorry, I didn't see your previous post. And yeah, I considered that (fuel expended when traveling would still force me to compute the distance traveled though). I considered a table-based Newton-Raphson, a log-based fast square root deal, some sort of octal representation to work it with bit shifts, partitioning the calculation over turns; lots of fun ideas.

Implementing them would probably have been fun as well, but pointless; the bottleneck wasn't there. It's a bad idea to optimize without measurement. Better to keep the routine simple, terse and expressive.

bikibird wrote:
Glad you have a solution that works for you. I haven't thought about those algorithms since I used to dabble with 6502 assembly language a very long time ago. Thanks for triggering the nostalgia


6502 always seemed like good clean fun. I'm doing 68k Asm through-and-through at the moment, and it's surprisingly coherent.

bikibird wrote:
I don't know Inform7 real well, but it seems to me that maybe instead of using a table to store this data, this is a job for a data graph, a.k.a relations. I'm not comfortable enough with Inform to figure out how to write that, but it seems like that relations might be a good fit for linking teleportation pads together?


It's a thought. zarf may correct me here, but IIRC, Inform 7 implements the many-to-many relation via tables under the hood.

bikibird wrote:
Been trying to improve my comp sci skills lately and have been studying a (very) little graph theory. There is a concept where the line (edge, link,relation, whatever you want to call it) has a weight value associated with it so that you can calculate the shortest distance between two nodes. For example consider cities linked by highways. What is the shortest path between two cities? That's different than fewest hops between cities. You have to take into account how long the roads are. Question: Does Inform7 have the ability to weight the relations between things? What would that code look like?


I'd love a link to that, because it sounds intriguing. As for I7 relations, they're strictly binary states. The usual idiom that I've seen for scalar relations is to use indirection: you implement with tables and phrases, add the required number of computed relations, and you'll have something that will act very much like what you want. The table itself will impose limitations on the design, however; you sacrifice the simplicity of just declaring a relation.

_________________
~Björn Paulsen


Top
 Profile Send private message  
Reply with quote  
PostPosted: Mon Sep 17, 2018 6:24 am 
Offline

Joined: Tue Mar 09, 2010 2:34 pm
Posts: 5360
Location: Burlington, VT
Oh yeah, if you want fuel expanded or anything like that you need the actual square roots.

I think many-to-many relations tend to be computationally expensive as far as I7 things go, because they have to store something for each pair of related things. Though as you said there's no point in trying to optimize things if you haven't profiled them.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Mon Sep 17, 2018 11:21 am 
Offline
User avatar

Joined: Mon Aug 28, 2017 12:07 pm
Posts: 42
Eleas wrote:
I'd love a link to that, because it sounds intriguing.


This should get you started.

https://en.wikipedia.org/wiki/Directed_graph

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Also take a look at the last example in the relationships chapter of the inform manual (244): http://inform7.com/learn/man/WI_13_16.html

Also can you clarify? Is your grid 16 x 16 (256 entries) or 256 x 256? If 16 x 16, have you thought about organizing a table this way with computed cost of the travel (time, distance, fuel, or whatever) as the values:

Code:
Table 2.1 - Travel Calculator 

Departure Alpha Beta Gamma Delta Epsilon
Alpha     0     10   20    30    40
Beta      10    0    10    20    30
Gamma     20    10   0     10    20
Delta     30    20   10    0     10
Epsilon   40    30   20    10    0


That should allow you to compute the cost of travel from Beta quadrant to Gamma quandrant for example.

The numbers are just examples of course, but notice how they line up over diagonal lines and reflect over the central diagonal going from top left to bottom right. That was not incidental and you can check for accuracy of data entry that way. I suppose you could do a 256 x 256 table, but the data entry would be unpleasant.

_________________
"She is not refined. She is not unrefined. She keeps a parrot."


Top
 Profile Send private message  
Reply with quote  
PostPosted: Mon Sep 17, 2018 12:09 pm 
Offline

Joined: Sat Jan 23, 2010 4:56 pm
Posts: 5754
The first thing to note is that the I7 "real square root of..." function makes use of the native sqrt() function. It's not slow.

(Integer square root does too, on Glulx.)

Quote:
It's a thought. zarf may correct me here, but IIRC, Inform 7 implements the many-to-many relation via tables under the hood.


The implementation uses an I6 array. It's memory-intensive, but I don't think it's CPU-intensive.


Top
 Profile Send private message  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 21 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 6 hours [ DST ]


Who is online

Users browsing this forum: Eleas, ralphmerridew and 9 guests


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

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