Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Skyrunner]

In Javascript, Infinity and NaN seem to be different concepts. Infinity is from the floating point specification, while NaN is a global property that automatically fails every comparison, including against itself. NaN should only be returned from functions that involve numbers and domains: Math.sqrt(-1) is one such example, and so is parseint("a").

edit: If you really don't want to use isNaN(), you can compare NaN to itself, since that's the only case a self-comparison would fail.

x = Math.sqrt(-1); x == x

[Telgin]

I've used the self comparison thing in JavaScript before to check for NaNs, which I agree is confusing but that's how it is.  I don't think anyone can blame JavaScript itself though, since I'm pretty sure several languages do that, even C and C++ I think.  Of course, many / all things that produce a NaN also generate floating point exceptions, but maybe those are trapped by the OS.  It's been a very long time since I've done anything like that in C or C++.

Also, people say that Python is very good for number crunching but my own experience has been the opposite.  It's easy to write the code, but very slow.  I guess people normally use libraries that are compiled as native code modules?  Doing heavy lifting in Python itself is pretty slow.

Fortran is technically pretty good for number crunching since it's compiled down like C, and you can probably find code examples to do most computations.  But... I wouldn't advise learning it since it's a relic from an age past that has not aged well.  The only people who use Fortran anymore are old programmers in scientific labs that haven't moved on to newer things and keep banging on the same unreadable codebases from 40 years ago.

[Skyrunner]

If you used Numpy and it was still slow, I have nothing to say. Generally, though, numpy is what people use for number crunching, and it's basically a wrapper around a C library specialized for handling multidimensional arrays of numbers only.

Also, you could always use isNaN() to check for NaN!

[Telgin]

No, it was all raw Python code so I'm not surprised that it was slow really.  I looked at a few computation libraries back when I was working on the project, but if I recall I couldn't figure out how to apply any of them directly to what I was doing so I didn't bother.  If they're wrappers around C code then I have no doubt they're much faster.  If I remember correctly, transitioning from raw Python code to C++ code compiled by Visual Studio was more than 5x faster and closer to 10x faster.

[Orange Wizard]

There's also... Cython, or something, that compiles Python code into C, without too much effort on the programmer's part. Even type declarations are optional IIRC.

[TheBiggerFish]

I have no idea what half of this is even talking about and I just barely sort of understand recursion.  Much yikes.
Looks interesting though.

[Putnam]

Hey, I developed a simple-ass webgame

it took me 12 hours of work, heh

[TheBiggerFish]

Not very mobile-friendly but I really cannot complain.

[i2amroy]

@Naxza
Filling the board is what you use Dijkstra's algorithm for. Just use the pseudocode given here ("vertex set" in this case would be a queue), and when you get to the "foreach neighbor" is where you would stick your check and addition to the queue for each of the 8 spots that a knight can visit from the previous one (assuming they aren't jumping off the board). There's no recursive nonsense needed in the slightest, everything is handled by a single while loop that keeps adding stuff to its own list of things to do.

The end result should be that Dijkstras slowly populates the entire board with numbers, with each corresponding to the lowest number of moves that it would take to reach that particular location and the particular spot that you jumped from to get there that fast.

[Putnam]

...oh, the mention of dijsktra's algorithm made me realize that my DFS I'm using to detect whether a board is solvable will not detect every solvable board due to the computational nightmare that is lemon-scented soap.

[Reelya]

Now implement Prim's algorithm and get yourself much better mazes. Plus, Prim's algorithm is guaranteed to make a traversable, perfect maze, in one pass.

Basically, the algorithm is :

- create / clear the map

- pick a random starting point, add that to an "open list", and mark it as "used" on the map.

- pop (remove) a random entry from the open list (for Prim's Algorithm) or the most recent entry (for recursive backtracker algorithm)

- check if there are any vacant neighbours (not used already). if so, pick one at random,

- make a tunnel to the neighbour, add the new node to the "open list", and mark it as used on the map

- once there are no nodes in the "open list" you are guaranteed of having a traversable space-filling maze!

[Putnam]

weighted undirected graph

it sure as hell ain't that lemme tell you

in fact, i'm fairly sure that it's better describable as an unweighted directed graph

[i2amroy]

...oh, the mention of dijsktra's algorithm made me realize that my DFS I'm using to detect whether a board is solvable will not detect every solvable board due to the computational nightmare that is lemon-scented soap.

If you were using dijkstras to check if the boards were solvable then it wouldn't be too much of a complexity increase. All you would need to do is to run it as a 3D array, where the "z-level" corresponds to your current flavor (and stepping on a flavor-changing tile automatically changes levels in the array). The maximum efficiency hit would just be going from ~O(V^2) to ~O((mV)^2), where m is the number of flavors (realistically it would be lower than that, since there would certainly be parts of the array where the flavors were mutually exclusive).

Course there's almost certainly some better algorithms out there, but the "z-level" idea to model scents could probably be applicable to at least some of them.

[Reelya]

Read this. This guys blog has an interactive demo which shows how the maze gets built.

http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm

The best bit about using Prim's algorithm for maze generation is that you only need to change 1 line of code to get this version:

http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking

[i2amroy]

Read this. I'm not going to have an argument about it, because this is just the way it's done, period. you can do it this way, or invent some bullshit way that's going to have problems.

http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm

Prim's would work, though once again you'd probably need to modify/expand it to some form of a 3D set of linked 2D slices to capture the scent logic, since attempting to capture it as a simple 2D slice is not going to be able to encapsulate the logical bool (or int if you wanted more scents than just 2) that the flavor scents require you to carry with you as you generate the maze outwards.