Search Results

Search found 16 results on 1 pages for 'bresenham'.

Page 1/1 | 1 

• Modifying Bresenham's line algorithm

  - by sphennings

  I'm trying to use Bresenham's line algorithm to compute Field of View on a grid. The code I'm using calculates the lines without a problem but I'm having problems getting it to always return the line running from start point to endpoint. What do I need to do so that all lines returned run from (x0,y0) to (x1,y1) def bresenham_line(self, x0, y0, x1, y1): steep = abs(y1 - y0) > abs(x1 - x0) if steep: x0, y0 = y0, x0 x1, y1 = y1, x1 if x0 > x1: x0, x1 = x1, x0 y0, y1 = y1, y0 if y0 < y1: ystep = 1 else: ystep = -1 deltax = x1 - x0 deltay = abs(y1 - y0) error = -deltax / 2 y = y0 line = [] for x in range(x0, x1 + 1): if steep: line.append((y,x)) else: line.append((x,y)) error = error + deltay if error > 0: y = y + ystep error = error - deltax return line

  Read the article

• Drawing Bresenham’s Line- Algorithm in all quadrants

  - by Yoyo2965259

  I am newbie for OpenGL. I am practicing the exercises from my textbook but I could not get the outputs which is should be in Bresenham's Line Algorithm in all quadrants. Here's the coding: #include <Windows.h> #include <GL/glut.h> void init(void) { glClearColor(0.0, 0.0, 0.0, 0.0); glShadeModel(GL_FLAT); } void BresnCir(void) { int delta, deltadash; glClear(GL_COLOR_BUFFER_BIT); glPointSize(3.0); int r = 150; int x = 0; int y = r; int D = 2 * (1 - r); glBegin(GL_POINTS); do { glVertex2i(x, y); if (D < 0) { delta = 2 * D + 2 * y - 1; if (delta <= 0) { x++; Right(x); } else { x++; y--; Diagonal(x, y); } glVertex2i(x, y); } else { deltadash = 2 * D - 2 * x - 1; if (deltadash <= 0) { x++; y--; Diagonal(x, y); } else { y--; Down(y); } glVertex2i(x, y); } if (D == 0) { x++; y--; Diagonal(x, y); glVertex2i(x, y); } } while (y > 0); glEnd(); glFlush(); } int main(int argc, char** argv) { glutInit(&argc, argv); glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB); glutInitWindowSize(400, 150); glutInitWindowPosition(100, 100); glutCreateWindow(argv[0]); init(); glutDisplayFunc(BresnCir); glutMainLoop(); return 0; } But, it keep comes out with errors C3861.

  Read the article

• efficient algorithm for drawing circle arcs?

  - by banister

  I am using the mid-point circle algorithm (bresenham circle) to efficiently draw whole circles. Is there something similar to draw circle arcs? I would like to specify a start angle and end angle and have only that portion of the circle drawn. Thanks in advance! EDIT: I would like to draw filled circle arcs too, i.e pie-slices. :)

  Read the article

• Diagonal line of sight with two corners

  - by Ash Blue

  Right now I'm using Bresenham's line algorithm for line of sight. The problem is I've found an edge case where players can look through walls. Occurs when the player looks between two corners of a wall with a gap on the other side at specific angles. The result I want is for the tile between two walls to be marked invalid as so. What is the fastest way to modify Bresenham's line algorithm to solve this? If there isn't a good solution, is there a better suited algorithm? Any ideas are welcome. Please note the solution should also be capable of supporting 3d. Edit: For the working source code and an interactive demo of the completed product please see http://ashblue.github.io/javascript-pathfinding/

  Read the article

• Plotting an Arc in Discrete Steps

  - by phobos51594

  Good afternoon, Background My question relates to the plotting of an arbitrary arc in space using discrete steps. It is unique, however, in that I am not drawing to a canvas in the typical sense. The firmware I am designing is for a gcode interpreter for a CNC mill that will translate commands into stepper motor movements. Now, I have already found a similar question on this very site, but the methodology suggested (Bresenham's Algorithm) appears to be incompatable for moving an object in space, as it only relies on the calculation of one octant of a circle which is then mirrored about the remaining axes of symmetry. Furthermore, the prescribed method of calculation an arc between two arbitrary angles relies on trigonometry (I am implementing on a microcontroller and would like to avoid costly trig functions, if possible) and simply not taking the steps that are out of the range. Finally, the algorithm only is designed to work in one rotational direction (e.g. counterclockwise). Question So, on to the actual question: Does anyone know of a general-purpose algorithm that can be used to "draw" an arbitrary arc in discrete steps while still giving respect to angular direction (CW / CCW)? The final implementation will be done in C, but the language for the purpose of the question is irrelevant. Thank you in advance. References S.O post on drawing a simple circle using Bresenham's Algorithm: "Drawing" an arc in discrete x-y steps Wiki page describing Bresenham's Algorithm for a circle http://en.wikipedia.org/wiki/Midpoint_circle_algorithm Gcode instructions to be implemented (see. G2 and G3) http://linuxcnc.org/docs/html/gcode.html

  Read the article

• Coordinate geometry operations in images/discrete space

  - by avd

  I have images which have line segments, rays etc. I am representing these line segments using Bresenham algorithm (means whatever coordinates I get using this algorithm between two points). Now I want to do operations such as finding intersection point between two line segments, finding the projection of one vector onto other etc... The problem is I am not working in continuous space. The line segments are being approximated using Bresenham algorithm. So I want suggestions on what are the best and most efficient ways to do this? A link to C++ library or implementation would also be good enough. Please suggest some books which deal with such problems.

  Read the article

• Given a start and end point, how can I constrain the end point so the resulting line segment is horizontal, vertical, or 45 degrees?

  - by GloryFish

  I have a grid of letters. The player clicks on a letter and drags out a selection. Using Bresenham's Algorithm I can create a line of highlighted letters representing the player's selection. However, what I really want is to have the line segment be constrained to 45 degree angles (as is common for crossword-style games). So, given a start point and an end point, how can I find the line that passes through the start point and is closest to the end point? Bonus: To make things super sweet I'd like to get a list of points in the grid that the line passes through, and for super MEGA bonus points, I'd like to get them in order of selection (i.e. from start point to end point).

  Read the article

• Tile-wide extent tracing on a grid.

  - by Larolaro

  I'm currently working on A* pathfinding on a grid and I'm looking to smooth the generated path, while also considering the extent of the character moving along it. I'm using a grid for the pathfinding, however character movement is free roaming, not strict tile to tile movement. To achieve a smoother, more efficient path, I'm doing line traces on a grid to determine if there is unwalkable tiles between tiles to shave off unecessary corners. However, because a line trace is zero extent, it doesn't consider the extent of the character and gives bad results (not returning unwalkable tiles just missed by the line, causing unwanted collisions). So what I'm looking for is rather than a line algorithm that determines the tiles under it, I'm looking for one that determines the tiles under a tile-wide extent line. Here is an image to help visualise my problem! Does anyone have any ideas? I've been working with Bresenham's line and other alternatives but I haven't yet figured out how to nail this specific problem.

  Read the article

• How can I render player movement on a 2d plane efficiently?

  - by user422318

  I'm prototyping a 2d HTML5 game with similar interaction to Diablo II. (See an older post of mine describing the interaction here: How can I imitate interaction and movement in Diablo II?) I just got the player click-to-move system working using the Bresenham algorithm but I can't figure out how to efficiently render the player's avatar as he moves across the screen. By the time redraw() is called, the player has already finished moving to the target point. If I try to call redraw() more frequently (based on my game timer), there's incredible system lag and I don't even see the avatar image glide across the screen. I have a game timer based off this awesome timer class: http://www.dailycoding.com/Posts/object_oriented_programming_with_javascript__timer_class.aspx In the future, there will be multiple enemies chasing the player. Fast pace is essential to the experience. What should I do?

  Read the article

• Effecient finding of long-range spotting targets

  - by nihohit

  I'm creating a top-down 2d strategy game, with a square grid map. So far, I've used Bresenham's line drawing algorithm in a circle to determine what's in LOS of each unit, and then targedt one of the targets in the circle. Now I find that this limits my units to shoot only at targets that they see. I want to extend my targeting algorithm to target any other unit in range of my weapon, even if they're out of sight range of this given unit, if they're "spotted" by another friendly unit. In other words, I want to enable usage of weapons with ranges longer than sight range. Is there a better way than iterating over all sighted units and computing range and LOSto each of them?

  Read the article

• Moving a unit precisely along a path in x,y coordinates

  - by Adam Eberbach

  I am playing around with a strategy game where squads move around a map. Each turn a certain amount of movement is allocated to a squad and if the squad has a destination the points are applied each turn until the destination is reached. Actual distance is used so if a squad moves one position in the x or y direction it uses one point, but moving diagonally takes ~1.4 points. The squad maintains actual position as float which is then rounded to allow drawing the position on the map. The path is described by touching the squad and dragging to the end position then lifting the pen or finger. (I'm doing this on an iPhone now but Android/Qt/Windows Mobile would work the same) As the pointer moves x, y points are recorded so that the squad gains a list of intermediate destinations on the way to the final destination. I'm finding that the destinations are not evenly spaced but can be further apart depending on the speed of the pointer movement. Following the path is important because obstacles or terrain matter in this game. I'm not trying to remake Flight Control but that's a similar mechanic. Here's what I've been doing, but it just seems too complicated (pseudocode): getDestination() { - self.nextDestination = remove_from_array(destinations) - self.gradient = delta y to destination / delta x to destination - self.angle = atan(self.gradient) - self.cosAngle = cos(self.angle) - self.sinAngle = sin(self.angle) } move() { - get movement allocation for this turn - if self.nextDestination not valid - - getNextDestination() - while(nextDestination valid) && (movement allocation remains) { - - find xStep and yStep using movement allocation and sinAngle/cosAngle calculated for current self.nextDestination - - if current position + xStep crosses the destination - - - find x movement remaining after self.nextDestination reached - - - calculate remaining direct path movement allocation (xStep remaining / cosAngle) - - - make self.position equal to self.nextDestination - - else - - - apply xStep and yStep to current position - } - round squad's float coordinates to integer screen coordinates - draw squad image on map } That's simplified of course, stuff like sign needs to be tweaked to ensure movement is in the right direction. If trig is the best way to do it then lookup tables can be used or maybe it doesn't matter on modern devices like it used to. Suggestions for a better way to do it? an update - iPhone has zero issues with trig and tracking tens of positions and tracks implemented as described above and it draws in floats anyway. The Bresenham method is more efficient, trig is more precise. If I was to use integer Bresenham I would want to multiply by ten or so to maintain a little more positional accuracy to benefit collisions/terrain detection.

  Read the article

• Finding which tiles are intersected by a line, without looping through all of them or skipping any

  - by JustSuds

  I've been staring at this problem for a few days now. I rigged up this graphic to help me visualise the issue: http://i.stack.imgur.com/HxyP9.png (from the graph, we know that the line intersects [1, 1], [1, 2], [2, 2], [2, 3], ending in [3,3]) I want to step along the line to each grid space and check to see if the material of the grid space is solid. I feel like I already know the math involved, but I haven't been able to string it together yet. I'm using this to test line of sight and eliminate nodes after a path is found via my pathfinding algorithms - my agents cant see through a solid block, therefore they cant move through one, therefore the node is not eliminated from the path because it is required to navigate a corner. So, I need an algorithm that will step along the line to each grid space that it intersects. Any ideas? I've taken a look at a lot of common algorithms, like Bresenham's, and one that steps at predefined intervals along the line (unfortunately, this method skips tiles if they're intersecting with a smaller wedge than the step size). I'm populating my whiteboard now with a mass of floor() and ceil() functions - but its getting overly complicated and I'm afraid it might cause a slowdown.

  Read the article

• extracting a quadrilateral image to a rectangle

  - by Will

  In the image below, the sign on the side of the van is not face-on to the camera. I want to calculate, as best I can with the pixels I have, what it'd look like face on. I imagine that this is some kind of loop through the x and y axis doing a Bresenham's line on both dimensions at once with some kind of mixing when pixels in the source image overlap - some sub-pixel mixing of some sort? What approaches are there, and how do you mix the pixels? Is there a standard approach for this?

  Read the article

• How can I tweak this A* search pathfinding algorithm to handle different terrain movement values?

  - by user422318

  I'm creating a 2D map-based action game with similar interaction design as Diablo II. In other words, the player clicks around a map to move their player. I just finished player movement and am moving on to pathfinding. In the game, enemies should charge the player's character. There are also five different terrain types that give different movement bonuses. I want the AI to take advantage of these terrain bonuses as they try to reach the player. I was told to check out the A* search algorithm (http://en.wikipedia.org/wiki/A*_search_algorithm). I'm doing this game in HTML5 and JavaScript, and found a version in JavaScript: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript I'm trying to figure out how to tweak it though. Below are my ideas about what I need to change. What else do I need to worry about? When I create a graph, I will need to initialize the 2D array I pass in passed on with a traversal of a map that corresponds to the different terrain types. in graph.js: "GraphNodeType" definition needs to be modified to handle the 5 terrain types. There will be no walls. in astar.js: The g and h scoring will need to be modified. How should I do this? in astar.js: isWall() should probably be removed. My game doesn't have walls. in astar.js: I'm not sure what this is. I think it indicates a node that isn't valid to be processed. When would this happen, though? At a high level, how do I change this algorithm from "oh, is there a wall there?" to "will this terrain get me to the player faster than the terrain around me?" Because of time, I'm also debating reusing my Bresenham algorithm for the enemies. Unfortunately, the different terrain movement bonuses won't be used by the AI, which will make the game suck. :/ I'd really like to have this in for the prototype, but I'm not a developer by trade nor am I a computer scientist. :D If you know of any code that does what I'm looking for, please share! Sanity check tips for this are also appreciated.

  Read the article

• Calculate new position of player

  - by user1439111

  Edit: I will summerize my question since it is very long (Thanks Len for pointing it out) What I'm trying to find out is to get a new position of a player after an X amount of time. The following variables are known: - Speed - Length between the 2 points - Source position (X, Y) - Destination position (X, Y) How can I calculate a position between the source and destion with these variables given? For example: source: 0, 0 destination: 10, 0 speed: 1 so after 1 second the players position would be 1, 0 The code below works but it's quite long so I'm looking for something shorter/more logical ====================================================================== I'm having a hard time figuring out how to calculate a new position of a player ingame. This code is server sided used to track a player(It's a emulator so I don't have access to the clients code). The collision detection of the server works fine I'm using bresenham's line algorithm and a raycast to determine at which point a collision happens. Once I deteremined the collision I calculate the length of the path the player is about to walk and also the total time. I would like to know the new position of a player each second. This is the code I'm currently using. It's in C++ but I am porting the server to C# and I haven't written the code in C# yet. // Difference between the source X - destination X //and source y - destionation Y float xDiff, yDiff; xDiff = xDes - xSrc; yDiff = yDes - ySrc; float walkingLength = 0.00F; float NewX = xDiff * xDiff; float NewY = yDiff * yDiff; walkingLength = NewX + NewY; walkingLength = sqrt(walkingLength); const float PI = 3.14159265F; float Angle = 0.00F; if(xDes >= xSrc && yDes >= ySrc) { Angle = atanf((yDiff / xDiff)); Angle = Angle * 180 / PI; } else if(xDes < xSrc && yDes >= ySrc) { Angle = atanf((-xDiff / yDiff)); Angle = Angle * 180 / PI; Angle += 90.00F; } else if(xDes < xSrc && yDes < ySrc) { Angle = atanf((yDiff / xDiff)); Angle = Angle * 180 / PI; Angle += 180.00F; } else if(xDes >= xSrc && yDes < ySrc) { Angle = atanf((xDiff / -yDiff)); Angle = Angle * 180 / PI; Angle += 270.00F; } float WalkingTime = (float)walkingLength / (float)speed; bool Done = false; float i = 0; while(i < walkingLength) { if(Done == true) { break; } if(WalkingTime >= 1000) { Sleep(1000); i += speed; WalkTime -= 1000; } else { Sleep(WalkTime); i += speed * WalkTime; WalkTime -= 1000; Done = true; } if(Angle >= 0 && Angle < 90) { float xNew = cosf(Angle * PI / 180) * i; float yNew = sinf(Angle * PI / 180) * i; float NewCharacterX = xSrc + xNew; float NewCharacterY = ySrc + yNew; } I have cut the last part of the loop since it's just 3 other else if statements with 3 other angle conditions and the only change is the sin and cos. The given speed parameter is the speed/second. The code above works but as you can see it's quite long so I'm looking for a new way to calculate this. btw, don't mind the while loop to calculate each new position I'm going to use a timer in C# Thank you very much

  Read the article

• HMTL5 Anti Aliasing Browser Disable

  - by Tappa Tappa

  I am forced to consider writing a library to handle the fundamental basics of drawing lines, thick lines, circles, squares etc. of an HTML5 canvas because I can't disable a feature embedded in the browser rendering of the core canvas algorithms. Am I forced to build the HTML5 Canvas rendering process from the ground up? If I am, who's in with me to do this? Who wants to change the world? Imagine a simple drawing application written in HTML5... you draw a shape... a closed shape like a rudimentary circle, free hand, more like an onion than a circle (well, that's what mine would look like!)... then imagine selecting a paint bucket icon and clicking inside that shape you drew and expecting it to be filled with a color of your choice. Imagine your surprise as you selected "Paint Bucket" and clicked in the middle of your shape and it filled your shape with color... BUT, not quite... HANG ON... this isn't right!!! On the inside of the edge of the shape you drew is a blur between the background color and your fill color and the edge color... the fill seems to be flawed. You wanted a straight forward "Paint Bucket" / "Fill"... you wanted to draw a shape and then fill it with a color... no fuss.... fill the whole damned inside of your shape with the color you choose. Your web browser has decided that when you draw the lines to define your shape they will be anti-aliased. If you draw a black line for your shape... well, the browser will draw grey pixels along the edges, in places... to make it look like a "better" line. Yeah, a "better" line that **s up the paint / flood fill process. How much does is cost to pay off the browser developers to expose a property to disable their anti-aliasing rendering? Disabling would save milliseconds for their rendering engine, surely! Bah, I really don't want to have to build my own canvas rendering engine using Bresenham line rendering algorithm... WHAT CAN BE DONE... HOW CAN THIS BE CHANGED!!!??? Do I need to start a petition aimed at the WC3???? Will you include your name if you are interested??? UPDATED function DrawLine(objContext, FromX, FromY, ToX, ToY) { var dx = Math.abs(ToX - FromX); var dy = Math.abs(ToY - FromY); var sx = (FromX < ToX) ? 1 : -1; var sy = (FromY < ToY) ? 1 : -1; var err = dx - dy; var CurX, CurY; CurX = FromX; CurY = FromY; while (true) { objContext.fillRect(CurX, CurY, objContext.lineWidth, objContext.lineWidth); if ((CurX == ToX) && (CurY == ToY)) break; var e2 = 2 * err; if (e2 > -dy) { err -= dy; CurX += sx; } if (e2 < dx) { err += dx; CurY += sy; } } }

  Read the article

1