| --- Log opened Thu Sep 01 00:00:10 2016 |
| 00:06 | <@celticminstrel> | What reason would an A* search have to assume a cost >= 1? |
| 00:08 | <&Derakon> | Pathing over mountains~ |
| 00:12 | <~Vornicus> | A* works better the closer the costing heuristic is to "correct" |
| 00:14 | <@celticminstrel> | Not sure what that means. |
| 00:14 | <&Derakon> | A reasonable predictor of the actual improvement in distance-to-goal. |
| 00:15 | <@celticminstrel> | So what does this have to do with ensuring cost >= 1? |
| 00:16 | <~Vornicus> | Here's a possibility: you have a square grid where the minimal cost for going orthogonally is 1 and the minimal cost for going diagonally is 1.5. Your A* costing heuristic will be closer to correct, and thus work better, when you say "diagonal moves count as costing 1.5" in the costing heuristic. This gives a cost heuristic of min(distance_to_goal.x, distance_to_goal.y) * 1 + max(distance_to goal.x, distance_to_goal.y) * 0.5 |
| 00:18 | <@celticminstrel> | "correct" here means "more likely to return the actual shortest path"? |
| 00:18 | <~Vornicus> | mmm, got those in the wrong order, it should be max * 1 + min * 0.5; this is as opposed to the overestimating and thus invalid (x+y)*1 taxicab distance or the worse-underestimating max(x,y)*1 chebyshev distance. |
| 00:18 | <~Vornicus> | Will select the shortest path with fewer false starts. |
| 00:19 | <@celticminstrel> | So it'll be faster on average? |
| 00:20 | <@celticminstrel> | Why does cost >= 1 make it closer to correct? |
| 00:20 | <~Vornicus> | Yes. The more accurate your cost heuristic is, the faster it will find the correct path, because it won't take paths and then discover that the cost to get there is higher than the heuristic says it should be. |
| 00:24 | <@celticminstrel> | So why does cost >= 1 make it closer to correct? |
| 00:24 | <~Vornicus> | As an example: say your thing's somewhere off to the northeast, say, 5 steps north and 3 steps east. |
| 00:25 | <~Vornicus> | Currently, cost heuristic is 5, and spent is 0. The cell 1 to the north has cost heuristic 4 and spent 1, for a total of 5; the cell 1 to the northeast has cost heuristic 4 and spent 1.5, so it's worse! |
| 00:26 | <~Vornicus> | ...except it's not actually worse. By choosing it we delay the inevitable by a while: eventually it has to go northeast. |
| 00:28 | <~Vornicus> | Now, if we instead use the weighted diagonal, so it counts the cost of going diagonally as 1.5 already, the distance to the goal is now 6.5 from the start; going north the cost goes down to 5.5 but we spend 1, so total is still 6.5; going northeast the cost goes down to 5, and we spend 1.5, so both paths have the correct cost still. |
| 00:30 | <~Vornicus> | The better the costing function, the less biased against expensive but actually optimal things it is. |
| 00:30 | <~Vornicus> | and so the sooner it takes the correct path. |
| 00:33 | <~Vornicus> | In this case, the cost heuristic uses a weight of 1.5 for diagonal paths, and this is closer to correct, so it works better. |
| 00:34 | | catalyst [catalyst@Nightstar-bt5k4h.81.in-addr.arpa] has quit [[NS] Quit: Leaving] |
| 00:35 | <@celticminstrel> | Still not clear on how this relates to ensuring costs >= 1, though. |
| 00:35 | | catadroid [catadroid@Nightstar-a6rhdp.dab.02.net] has joined #code |
| 00:35 | <~Vornicus> | I think I'm missing something here. |
| 00:35 | <~Vornicus> | What costs are >=1? |
| 00:36 | <~Vornicus> | Those of actual paths? |
| 00:36 | <@celticminstrel> | I think it's the cost of entering a given tile? |
| 00:36 | <~Vornicus> | okay. |
| 00:36 | <~Vornicus> | I think I see what's actually happening here. |
| 00:36 | <@celticminstrel> | (Guessing it's not important, but this is also a hexagonal map.) |
| 00:37 | <~Vornicus> | Your A*'s cost heuristic is naive in the following way: it uses exactly the hexagon distance between source and destination. |
| 00:37 | <~Vornicus> | And so *the cost heuristic* assumes each path has cost 1. |
| 00:37 | <~Vornicus> | A* only works when the cost heuristic underestimates actual cost, right |
| 00:38 | <~Vornicus> | Well, at most underestimates. It's allowed to be exactly right, but it's not allowed to overestimate. |
| 00:39 | <~Vornicus> | But if a path has cost < 1, then A* will overestimate the cost for that path. |
| 00:40 | <@celticminstrel> | I see. |
| 01:03 | | macdjord [macdjord@Nightstar-r9vt2h.mc.videotron.ca] has joined #code |
| 01:03 | | mode/#code [+o macdjord] by ChanServ |
| 02:12 | | catadroid` [catadroid@Nightstar-7b7li2.dab.02.net] has joined #code |
| 02:15 | | catadroid [catadroid@Nightstar-a6rhdp.dab.02.net] has quit [Ping timeout: 121 seconds] |
| --- Log closed Thu Sep 01 02:28:30 2016 |
| --- Log opened Thu Sep 01 02:28:39 2016 |
| 02:28 | | TheWatcher [chris@GlobalOperator.Nightstar.Net] has joined #code |
| 02:28 | | Irssi: #code: Total of 41 nicks [35 ops, 0 halfops, 0 voices, 6 normal] |
| 02:28 | | mode/#code [+o TheWatcher] by ChanServ |
| 02:29 | | Irssi: Join to #code was synced in 52 secs |
| 02:58 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has quit [Ping timeout: 121 seconds] |
| 02:59 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has joined #code |
| 03:11 | | ion_ [Owner@Nightstar-oj1.09k.65.184.IP] has joined #code |
| 03:13 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has quit [Ping timeout: 121 seconds] |
| 04:01 | | VirusJTG [VirusJTG@Nightstar-6i5vf7.sta.comporium.net] has quit [Connection closed] |
| 05:04 | | JustBob [justbob@Nightstar.Customer.Dissatisfaction.Administrator] has quit [Ping timeout: 121 seconds] |
| 05:15 | | Derakon is now known as Derakon[AFK] |
| 05:35 | | Netsplit Deepthought.Nightstar.Net <-> Golgafrincham.Nightstar.Net quits: @himi, catadroid`, gizmore |
| 05:36 | | Netsplit over, joins: @himi, catadroid`, gizmore |
| 05:51 | | JustBob [justbob@ServerAdministrator.Nightstar.Net] has joined #code |
| 05:51 | | mode/#code [+o JustBob] by ChanServ |
| 06:18 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has joined #code |
| 06:21 | | ion_ [Owner@Nightstar-oj1.09k.65.184.IP] has quit [Ping timeout: 121 seconds] |
| 06:26 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has quit [Ping timeout: 121 seconds] |
| 06:28 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has joined #code |
| 06:40 | | Kindamoody[zZz] is now known as Kindamoody |
| 07:17 | | catadroid` is now known as catadroid |
| 07:20 | | JustLurk [justbob@ServerAdministrator.Nightstar.Net] has joined #code |
| 07:20 | | JustBob [justbob@Nightstar.Customer.Dissatisfaction.Administrator] has quit [NickServ (RECOVER command used by JustLurk)] |
| 07:20 | | JustLurk is now known as JustBob |
| 07:20 | | mode/#code [+o JustBob] by ChanServ |
| 07:21 | | Netsplit Deepthought.Nightstar.Net <-> Golgafrincham.Nightstar.Net quits: catadroid, ion, @himi, gizmore |
| 07:22 | | Netsplit over, joins: @himi, catadroid, gizmore, ion |
| 07:48 | < catadroid> | Apparently I'm nearly single handedly responsible for us having tools that approach what other AAA companies have for our content guys instead of basically just notepad. I'm not sure that's exactly true, but I should certainly not feel worthless :o |
| 07:51 | | gnolam [lenin@Nightstar-t1tbf0.cust.bahnhof.se] has quit [Ping timeout: 121 seconds] |
| 07:55 | | * Vornicus bows before catadoggess |
| 07:55 | <~Vornicus> | ...catagoddess |
| 07:56 | <&McMartin> | A lady doge is a dogaressa |
| 07:58 | <~Vornicus> | such nobility |
| 08:01 | | himi [sjjf@Nightstar-dm0.2ni.203.150.IP] has quit [Ping timeout: 121 seconds] |
| 08:15 | < catadroid> | x) |
| 08:15 | < catadroid> | Source on that: our head of animation |
| 08:18 | | gnolam [lenin@Nightstar-t1tbf0.cust.bahnhof.se] has joined #code |
| 08:18 | | mode/#code [+o gnolam] by ChanServ |
| 08:20 | | Kindamoody [Kindamoody@Nightstar-0lgkcs.tbcn.telia.com] has quit [Ping timeout: 121 seconds] |
| 08:20 | | Kindamoody [Kindamoody@Nightstar-0lgkcs.tbcn.telia.com] has joined #code |
| 08:20 | | mode/#code [+o Kindamoody] by ChanServ |
| 08:22 | <~Vornicus> | catadroid: put that shit on your resume |
| 08:26 | | Kindamoody is now known as Kindamoody|out |
| 08:27 | | gnolam [lenin@Nightstar-t1tbf0.cust.bahnhof.se] has quit [Ping timeout: 121 seconds] |
| 08:29 | | catalyst [catalyst@Nightstar-bt5k4h.81.in-addr.arpa] has joined #code |
| 08:32 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has quit [Ping timeout: 121 seconds] |
| 08:34 | | gnolam [lenin@Nightstar-t1tbf0.cust.bahnhof.se] has joined #code |
| 08:34 | | mode/#code [+o gnolam] by ChanServ |
| 08:35 | | * Vornicus does some math. assuming I can get a regular physics system to go "moving at less than 3m/s? no bounce at all" then my most ludicrous candidate velocity of 40 m/s would require an angle of... huh. only 4.2 deg to prevent curve intakes from causing bounce. If the physics system is smart enough to notice the first edge something would hit. |
| 08:35 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has joined #code |
| 08:41 | <~Vornicus> | But having seen the kind of bs physics systems pull I have no real reason to believe that happens. arg. |
| 08:42 | | catadroid` [catadroid@Nightstar-aso020.dab.02.net] has joined #code |
| 08:43 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has quit [Ping timeout: 121 seconds] |
| 08:45 | | catadroid [catadroid@Nightstar-7b7li2.dab.02.net] has quit [Ping timeout: 121 seconds] |
| 08:46 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has joined #code |
| 08:59 | | celticminstrel [celticminst@Nightstar-ehtgrr.dsl.bell.ca] has quit [[NS] Quit: And lo! The computer falls into a deep sleep, to awake again some other day!] |
| 09:08 | | ion_ [Owner@Nightstar-oj1.09k.65.184.IP] has joined #code |
| 09:10 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has quit [Ping timeout: 121 seconds] |
| 09:13 | <~Vornicus> | And using straight lines anyway will reduce the ball speed with the bumps where a real curve wouldn't, though I can't say off the top how much, comparatively. 'course if I get full access to collisions including timing, normals, velocities, and all that shit, I can probably fake it, but |
| 09:14 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has joined #code |
| 09:15 | | catalyst [catalyst@Nightstar-bt5k4h.81.in-addr.arpa] has quit [[NS] Quit: Leaving] |
| 09:16 | | ion_ [Owner@Nightstar-oj1.09k.65.184.IP] has quit [Ping timeout: 121 seconds] |
| 09:38 | | gizmore|2 [kvirc@Nightstar-g7q22k.dip0.t-ipconnect.de] has joined #code |
| 09:38 | | gizmore [kvirc@Nightstar-05cl35.dip0.t-ipconnect.de] has quit [Ping timeout: 121 seconds] |
| 09:55 | | ion [Owner@Nightstar-oj1.09k.65.184.IP] has quit [Ping timeout: 121 seconds] |
| 10:16 | | Emmy-zZz is now known as Emmy |
| 10:17 | <@Emmy> | whactcha trying to pull, Vornicus? |
| 10:19 | <~Vornicus> | I want inside circles. Physics engines don't have them. I know how to write them, but I can't add them to existing physics systems, and making my own involves among other things circle-parabola intersection, which is a quartic. |
| 10:20 | <~Vornicus> | I've been fighting with quartics for a week and wanted to see if it was sensible to give up and try physics engines but I haven't had any luck determining if these engines are up to snuff. |
| 10:20 | <~Vornicus> | and I've seen a lot of really bad physics that happened because somebody decided to use an existing physics engine naively. |
| 10:22 | <~Vornicus> | Meanwhile I have something half written that allows me to use inside circles and all the other things and can actually handle hitting something and continuing in the same frame, which is another thing I have no idea if existing engines can handle. |
| 10:24 | <~Vornicus> | it's not perfect - travelling along a circle under force of gravity is a nonlinear second order ODE, and in order to get accuracy in root finding I'm using euler's method which sucks but at least it gives me a quadratic. |
| 10:55 | | VirusJTG [VirusJTG@Nightstar-6i5vf7.sta.comporium.net] has joined #code |
| 10:55 | | mode/#code [+ao VirusJTG VirusJTG] by ChanServ |
| 11:05 | | catadroid` is now known as catadroid |
| 11:06 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has quit [Ping timeout: 121 seconds] |
| 13:30 | | himi [sjjf@Nightstar-v37cpe.internode.on.net] has joined #code |
| 13:30 | | mode/#code [+o himi] by ChanServ |
| 15:12 | | catadroid` [catadroid@Nightstar-pnc547.dab.02.net] has joined #code |
| 15:16 | | catadroid [catadroid@Nightstar-aso020.dab.02.net] has quit [Ping timeout: 121 seconds] |
| 15:17 | | celticminstrel [celticminst@Nightstar-ehtgrr.dsl.bell.ca] has joined #code |
| 15:17 | | mode/#code [+o celticminstrel] by ChanServ |
| 16:08 | | gizmore|2 [kvirc@Nightstar-g7q22k.dip0.t-ipconnect.de] has quit [Operation timed out] |
| 16:08 | | gizmore|2 [kvirc@Nightstar-vo9c7g.dip0.t-ipconnect.de] has joined #code |
| 16:10 | | Derakon[AFK] is now known as Derakon |
| 16:54 | | catadroid` is now known as catadroid |
| 18:39 | | Emmy [Emmy@Nightstar-9p7hb1.direct-adsl.nl] has quit [Ping timeout: 121 seconds] |
| 18:41 | | Kindamoody|out is now known as Kindamoody |
| 20:41 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 20:42 | | mode/#code [+qo Vornicus Vornicus] by ChanServ |
| 21:08 | | catalyst [catalyst@Nightstar-bt5k4h.81.in-addr.arpa] has joined #code |
| 21:24 | | catalyst [catalyst@Nightstar-bt5k4h.81.in-addr.arpa] has quit [[NS] Quit: Leaving] |
| 21:39 | | gizmore|2 [kvirc@Nightstar-vo9c7g.dip0.t-ipconnect.de] has quit [A TLS packet with unexpected length was received.] |
| 21:42 | | catadroid` [catadroid@Nightstar-23iq15.dab.02.net] has joined #code |
| 21:45 | | catadroid [catadroid@Nightstar-pnc547.dab.02.net] has quit [Ping timeout: 121 seconds] |
| 22:56 | | Kindamoody is now known as Kindamoody[zZz] |
| --- Log closed Fri Sep 02 00:00:26 2016 |