Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!

1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Member Since 07 Mar 2002
Offline Last Active Yesterday, 11:14 PM

#5197396 how to know the number of different paths in a given graph

Posted by Álvaro on 10 December 2014 - 09:56 AM

If the adjacency matrix is M and the length is l, M^l times a column vector that has a 1 in the position of the start node and 0s elsewhere will be a column vector that tells you how many paths of length l there are from that start node to any other node. Pick the coordinate corresponding to your target node, and you'll be done.

#5196384 Is there algorithm for boxcasting or thickray casting?

Posted by Álvaro on 04 December 2014 - 10:43 PM

There were several details you got wrong. Here's a fixed version:

function visit_cells_in_box_sweep(x, y, vx, vy, halfWidth, max_t){
    var floor = Math.floor;
    var min = Math.min;

    var A = vy;
    var B = -vx;
    var min_C = A * (x - halfWidth) + B * (y + halfWidth);
    var max_C = A * (x + halfWidth) + B * (y - halfWidth);
    var next_horizontal = fmod(1.0 - y, 1.0)/vy;
    var next_vertical = fmod(1.0 - x, 1.0)/vx;

    var last_cell_x = floor(x);
    var last_cell_y = floor(y);

    var _ = 100; // break out of infinite loop just in case
    while (_>0){
        var next = min(next_horizontal, next_vertical);
        if (next >= max_t)
        var rx = x + next * vx;
        var ry = y + next * vy;
        var cx;
        var cy;
        if (next_horizontal < next_vertical){
            next_horizontal += 1.0/ vy;
            cx = floor(rx);
            cy = floor(ry+.5);
        } else {
            next_vertical += 1.0/ vx;
            cx = floor(rx+.5);
            cy = floor(ry);
        if (cy > last_cell_y){
            // new row
            for (var _x = cx - 1; A * (_x+1) + B * cy >= min_C; --_x){
                plotColored(_x, cy, 10, "red");
                //console.log(_x, _y);
        if (cx > last_cell_x){
            // new columns
            for (var _y = cy - 1; A * cx + B * (_y+1) <= max_C; --_y){
                plotColored(cx, _y, 10, "blue");
                //console.log(cx, _y);
        if (cx !== last_cell_x || cy !== last_cell_y){
            plotColored(cx, cy, 10, "black");
           // console.log(cx,cy);
            last_cell_x = cx;
            last_cell_y = cy;

    x *= 10;
    y *= 10;
    vx *= 10;
    vy *= 10;
    halfWidth *= 10;
    ctx.strokeStyle = "red";

    ctx.strokeRect(x-halfWidth, y-halfWidth, halfWidth*2, halfWidth*2);

#5196371 Is there algorithm for boxcasting or thickray casting?

Posted by Álvaro on 04 December 2014 - 08:59 PM

Here, I implemented my own ray cast algorithm and the I modified so every time a new row is visited, all required cells to the right of the new cell are also visited, and similarly with new columns. The code I wrote only works in the case where the ray has a vector with positive x and y coordinates. So if you want to use my code, you'll have to change it to make it work in every case; this is just a proof of concept. [EDIT: Skip down to `visit_cells_in_box_sweep' to get to the meat of the code.]
#include <iostream>
#include <cmath>

struct Vector {
  float x, y;
  Vector(float x, float y) : x(x), y(y) {

Vector operator*(float s, Vector const &v) {
  return Vector(s * v.x, s * v.y);

float dot(Vector const &v1, Vector const &v2) {
  return v1.x * v2.x + v1.y * v2.y;

float length(Vector const &v) {
  return std::sqrt(dot(v,v));

Vector normalized(Vector const &v) {
  return (1.0f / length(v)) * v;

struct Point {
  float x, y;
  Point(float x, float y) : x(x), y(y) {

Point operator+(Point const &p, Vector const &v) {
  return Point(p.x + v.x, p.y + v.y);

struct Ray {
  Point p;
  Vector v;
  Ray(Point const &p, Vector const &v) : p(p), v(v) {
  Point at(float t) const {
    return p + t * v;

struct Cell {
  int x, y;
  Cell(int x, int y) : x(x), y(y) {
  Cell() = default;
  Cell(Cell const &) = default;

bool operator==(Cell const &c1, Cell const &c2) {
  return c1.x == c2.x && c1.y == c2.y;

bool operator!=(Cell const &c1, Cell const &c2) {
  return !(c1 == c2);

template <typename Function>
void visit_cells_in_box_sweep(Ray const &ray, float half_width, Function f, float max_t) {
  float A = ray.v.y;
  float B = -ray.v.x;
  float min_C = A * (ray.p.x - half_width) + B * (ray.p.y + half_width);
  float max_C = A * (ray.p.x + half_width) + B * (ray.p.y - half_width);
  float next_horizontal = std::fmod(1.0f - ray.p.y, 1.0f) / ray.v.y;
  float next_vertical = std::fmod(1.0f - ray.p.x, 1.0f) / ray.v.x;
  Cell last_cell(int(std::floor(ray.p.x)), int(std::floor(ray.p.y)));
  while (1) {
    float next = std::min(next_horizontal, next_vertical);
    if (next >= max_t)
    Point intersection = ray.at(next);
    Cell cell;
    if (next_horizontal < next_vertical) {
      next_horizontal += 1.0f / ray.v.y;
      cell = Cell(int(std::floor(intersection.x)), int(std::round(intersection.y)));
    else {
      next_vertical += 1.0f / ray.v.x;
      cell = Cell(int(std::round(intersection.x)), int(std::floor(intersection.y)));
    if (cell.y > last_cell.y) {
      // New row
      for (int x = cell.x - 1; A * (x + 1) + B * cell.y >= min_C; --x)
    f(Cell(x, cell.y));
    if (cell.x > last_cell.x) {
      // New columns
      for (int y = cell.y - 1; A * cell.x + B * (y + 1) <= max_C; --y)
    f(Cell(cell.x, y));
    if (cell != last_cell)
    last_cell = cell;

void print_cell(Cell const &cell) {
  std::cout << "Visiting cell at (" << cell.x << "," << cell.y << ")\n";

int main() {
  Ray ray(Point(10.75f, 5.5f), normalized(Vector(0.5f, 1.0f)));
  visit_cells_in_box_sweep(ray, 0.5f, print_cell, 10.f);

#5196140 Pseudo 3D screen projection issue

Posted by Álvaro on 03 December 2014 - 03:31 PM

How would the equivalent look in Wolfram Alpha after you adjusted it according to my coordinates?

It would look like this.

#5196105 Pseudo 3D screen projection issue

Posted by Álvaro on 03 December 2014 - 12:03 PM

I think you are changing your mind as to whether the board is 1600 units long or 3200 units long.


Here we go again:


const double A = -2971600.0 / 313.0;
const double B = 21.0 / 5008.0;
const double C = -9200.0 / 313.0;

#5196097 Pseudo 3D screen projection issue

Posted by Álvaro on 03 December 2014 - 11:11 AM

I am guessing I didn't understand your coordinate conventions, then. Try this:


const double A = -1485800.0 / 313.0;
const double B = 21.0 / 5008.0;
const double C = -4600.0 / 313.0;

#5196075 Pseudo 3D screen projection issue

Posted by Álvaro on 03 December 2014 - 08:51 AM

I took the image you posted and I measured on it that the bottom of the board is at y=394, the top is at y=323 and the middle is at y=348. If I think of those points as having z=0, z=3200 and z=1600 respectively, I know that the mapping from z to y has to be a homography, which basically means it has to be of the form


y = (z + A) / (B * z + C)


By plugging in the three points I measured into that formula, we get a system of linear equations in A,B,C, which you can solve using Wolfram Alpha.

double y_from_z(double z) {
  const double A = 1970000.0 / 313.0;
  const double B = 21.0 / 5800.0;
  const double C = 5000.0 / 313.0;
  return (z + A) / (B * z + C);

Can you check if that part works? If it does, we can then figure out how to change the x coordinate with depth.


#5195917 Chatbot in 18 lines of code (Python) help.

Posted by Álvaro on 02 December 2014 - 01:04 PM

On a related note: http://xkcd.com/221/



#5195916 Chatbot in 18 lines of code (Python) help.

Posted by Álvaro on 02 December 2014 - 01:02 PM

I'm not a python expert, but wouldn't you need to have the random.choice bits of code in the while bit?


Oh, right! I now understand what the OP was talking about.


import random

greetings = ['hola', 'hello', 'hi', 'Hi', 'hey!','hey']

question = ['How are you?','How are you doing?']
responses = ['Okay',"I'm fine"]

while True:
        userInput = raw_input(">>> ")
        if userInput in greetings:
                random_greeting = random.choice(greetings)
        elif userInput in question:
                random_response = random.choice(responses)
                print("I did not understand what you said")

#5195877 Unity or C++?

Posted by Álvaro on 02 December 2014 - 07:33 AM

Although you can certainly make games with Unity I find it a little strange how many people here are making some implication that you'll become some great all knowing developer by using nothing but Unity.

I didn't get the impression that people were implying that.

How would you actually learn about how things work under the hood without implementing them yourself? I really doubt I'm going to walk up to someone that has only used Unity and ask them details about implementing anything in DirectX and expect any kind of useful answer, or how to deal with low level input handling and architecture between game subsystems. Frankly they won't even know a lot of those systems exist or how they work, they'll just understand the interfaces they've grown to use to interact with them.

There are many levels involved in software development. You can arrange gates in FPGAs to get something done, or use assembly language, or do systems programming in C, or program in a mid-level language, or you can use a high-level tool for a specific type of software, like the ones we are discussing here. Of course expertise at one of these levels doesn't automatically grant you knowledge about the whole thing. People are just saying that there is nothing wrong with programming at the high level.

On the other hand you aren't going likely to be writing any of the underlying code that powers unity anytime soon either, without learning it. You're stuck with the tools Unity gives you.

Yes, one does sacrifice fine control and flexibility by using a high-level tool. That is a trade-off that needs to be learned. Whenever he encounters those problems, he'll have good motivation to try his hand at a lower-level setup.

The way my mind works, it was better for me to learn the lower levels first (starting with assembly language and systems programming), so at all times I had the feeling that I essentially understood how things worked internally. But not everybody learns the same way. Starting at the top and working your way down can be very effective as well.

#5195609 *. not the same as ->

Posted by Álvaro on 30 November 2014 - 09:01 PM

You keep asking the worst questions in the forum. Please, learn to ask questions. If you have some line of code that doesn't compile, for Poseidon's sake, show us the line and the corresponding compiler error.

#5195370 find the closest vector to point

Posted by Álvaro on 29 November 2014 - 12:58 PM

The dot products of the vector F-A with the two normal vectors have different signs. Pick the positive one.

#5195120 programming a 3D board

Posted by Álvaro on 28 November 2014 - 02:04 AM

Where do you get 136 from? I count 152 or 144, depending on whether the corner triangles count or not.

#5194931 Quick C++ question on pointers

Posted by Álvaro on 27 November 2014 - 04:12 AM

Why do you need a class specifically for modifying another? Why don't you want the original class modifying itself?

It's not a class, really. It's just a bunch of free functions that have been unfortunately packed into a class for no apparent reason. But yes, they don't seem to provide anything beyond what members of the class they take as first argument already provide.

#5194841 Quick C++ question on pointers

Posted by Álvaro on 26 November 2014 - 03:44 PM

It sounds like you changed your code since the last time you posted it. Can you post some piece of code and a clear description of what the problem is?

I'll try to help you, even though your code seems to be affected by the former-Java-programmer disease. smile.png