|
There must be an algorithm somewhere you can copy, I think I adapted one I found. Google line intersect c# or something. I reckon that could do all the tests for you really fast.
|
#
?
Apr 14, 2019 21:13
|
|
|
|
| # ? May 11, 2024 16:19 |
|
|
If your goal is to get a reasonably-spaced set of vertices and edges, look up Delaunay triangulations. They're closely related to Voronoi diagrams, which leper khan already brought up.
|
|
#
?
Apr 14, 2019 21:38
|
|
|
I don't mind the overlapping paths - they would definitely exist in real life and I don't think they make it confusing to read.
|
|
#
?
Apr 14, 2019 21:44
|
|
|
Eve Online has overlapping paths just like you've showed. However, each point is a representation of three dimensional space and they allow you to rotate the map which makes clear that the points aren't really as close together as they look from a particular view point. I think doing something like Voronoi might make it look too unnatural if your goal is to have it look like stars in space. Your best bet would be to have tweak able parameters like: - a minimum distance between points - a cluster maximum, eg. only allow X number of stars to be clumped together within a certain distance of each other - minimum & maximum length of a line - maximum times a line can be crossed by another line / maximum times a line can cross other lines - minimum distance allowed for a line passing by a point - maximum lines to a single point xgalaxy fucked around with this message at 22:04 on Apr 14, 2019 |
|
#
?
Apr 14, 2019 21:55
|
|
|
Kibbles n Shits posted:I think if I can just figure out a cheap way to remove the intersecting lanes These are just line segments, and look very limited in length, so a simple sweep line algorithm should suffice.
|
|
#
?
Apr 14, 2019 22:10
|
|
|
Kibbles n Shits posted:Can anyone recommend what data structure or techniques I should be researching to make a convincing galactic map where the stars are connected via warp lanes in a logical manner, as seen in Stellaris or Space Empires IV for example. I've been experimenting with connecting them based on distance but not only is it god awfully slow, the results usually look like a cluster gently caress How big do you want the map to be when the game is done?
|
|
#
?
Apr 14, 2019 22:23
|
|
|
Broken Loose posted:How big do you want the map to be when the game is done? This very hypothetical finished game would probably have 500 stars at the upper limit, with a "standard map" being in the 200 to 300 range. Maybe even less, I'm not sure, but 500 seems like a good theoretical limit. Kibbles n Shits fucked around with this message at 22:30 on Apr 14, 2019 |
|
#
?
Apr 14, 2019 22:28
|
|
|
xgalaxy posted:Eve Online has overlapping paths just like you've showed. However, each point is a representation of three dimensional space and they allow you to rotate the map which makes clear that the points aren't really as close together as they look from a particular view point. You could use an algorithm similar to Poisson disk sampling for the star generation perhaps: randomly select initial points on a grid, so that each grid square contains at most one point. Generate k candidate points at random within an annulus (between r and 2r from the initial point for some r) around each initial point. If the candidate point is no closer than r to any other points, insert it. If not, discard it. Generally you want your points fairly dense across the entire space so you ensure one initial point per grid square, however if you want more sparsely distributed clusters you could just select some squares at random to place an initial point instead. Likewise you usually use constant k to maintain density, but if you vary it your clusters will be differently sized. There are some pretty fast and easily implemented Poisson disk sampling algorithms out there if you take a look around and it's easily adapted to 3D too, I've found it very useful for generating random-looking but nicely spaced noise.
|
|
#
?
Apr 15, 2019 00:16
|
|
|
Kibbles n Shits posted:I've been tweaking the parameters, I think if I can just figure out a cheap way to remove the intersecting lanes, it will be exactly what I want. Determining if two segments intersect is super easy. You got the XY of each end of the segments so just plug it in. https://www.topcoder.com/community/competitive-programming/tutorials/geometry-concepts-line-intersection-and-its-applications/ If it's only done once at map creation I don't think it needs to be mega optimized. Brute force every single segment against every other one if you have to and get smarter when/if it becomes a problem.
|
|
#
?
Apr 15, 2019 00:51
|
|
|
If you're already having problems with the generation being slow then it sounds like just testing everything against everything is actually an issue at this point. I'm a bit surprised that it's already problematic with 500 stars since that's just ~250k possible connections total which doesn't seem like that big a deal, but oh well. Anyhow, if you need to do things like query all stars within distance k of a point p, find the closest star to another star, get all connections within a region, do hyperlane intersecton tests and so on without having to loop through every single star and connection you'll need to use spatial acceleration structures for your stars and hyperlanes. 500 stars is not a lot as spatial data goes so you're probably best off using something simple and cheap to update like a grid or quadtree. If terms like spatial acceleration structure, BVH and quadtree are unfamiliar then I think they're probably good things to google before you go further. You also probably want to look into some type of stratified sampling and blue noise random sequences. Poisson sampling is one possibility, and works well if you know exactly how many samples you need beforehand, which is true for placing stars. If you need something more dynamic you can look at other low discrepancy sampling techniques like grid stratification or fixed sequences like Halton or Hammersley, etc. A very common approach for high quality blue noise is to just pre-generate a sequence or two of points that have perfect blue noise characteristics for the first k numbers, using some slow method like dart throwing. For sampling you then use some random rotation of that hardcoded, high-quality sequence. Again, if any of these terms are completely unfamiliar then googling Poisson disk sampling, blue noise sampling, low discrepancy sampling, the Halton, Hammerlsey and Sobol sequences, jittered sampling, and so on is probably a good idea. The key thing is that you absolutely do not want uniformly distributed noise for a lot of the things you're trying to do: you want something that avoids placing any two samples/stars near each another yet is still roughly evenly distributed over the sample space. I rather like sampling things so I'd be inclined to try and solve the connection problem itself by randomly sampling stars from the set and trying to connect them until I've reached a threshold for sufficiently connected. Something like code:I remember trying to figure out Stellaris' approach in the patch after they switched to hyperlane only. I think they start the map generation by generating a minimum spanning tree for the initial hyperlanes, with an extra constraint of avoiding collisions plus some some extra weight for edges across the void between arms in spiral galaxy. Then they add random new lanes and wormholes to satisfy the player's specified lane and wormhole density parameters, in some way. That might be a complete misread, not like I've seen the code. Alternatively you can start with a Delaunay triangulation and randomly add/delete connections to make it less well-ordered. That would be faster, but seems harder to control. For the star positions, I'd be inclined to go with a two step process to be able to control the galaxy appearance: First, generate a small (256x256 or so?) density map roughly matching some particular galaxy shape. N-arm spiral, uniform disk, attenuated ellipsis, bar, etc. Easiest and fastest to paint them manually, if you don't feel like finding a good algorithmic approximation. The algorithmic approach would involve finding a formula for a very regular galaxy of the requested type, then doing the usual adding of a couple octaves of Perlin noise to offset things like the spiral arm positions and final density map in order to get something nice. Second, sample points on the density map using some aforementioned blue noise type distribution. The advantage of having a nice, noisy density map to begin with is that you can get away with doing this very cheaply and don't need a high quality sequence.
|
|
#
?
Apr 15, 2019 01:32
|
|
|
Wow, I appreciate you taking the time to write all that up. Unfortunately much of it is lost on my puny brain. As a personal project that will never see the light of day I think a "test every line against every other line" naive approach will be good enough. I clearly have much to learn. I'll probably end up closer to 200 stars at the high end, as this increasingly hypothetical space 4X game would be balanced around shorter playthroughs.
Kibbles n Shits fucked around with this message at 04:03 on Apr 15, 2019 |
|
#
?
Apr 15, 2019 03:59
|
|
|
Kibbles n Shits posted:Wow, I appreciate you taking the time to write all that up. Unfortunately much of it is lost on my puny brain. As a personal project that will never see the light of day I think a "test every line against every other line" naive approach will be good enough. I clearly have much to learn. I'll probably end up closer to 200 stars at the high end, as this increasingly hypothetical space 4X game would be balanced around shorter playthroughs.
|
|
#
?
Apr 15, 2019 04:25
|
|
|
I'm into dirty simple tricks so I would generate a huuge source starmap with like 10k-100k stars as a mesh object in a 3D modeling software. It would be very easy to control the look and feel of the results and ensure that there are no overlapping paths or other, possibly even game breaking, edge cases. The mesh would be pretty simple to model procedurally: just generate a plane that has a random but pleasant-looking distribution of vertices on it and then delete bunch of vertices from it to punch holes in it. You may want to drive the vertex deletion with a perlin noise or similar instead of a pure random chance so that the granularity of the holes can be controlled. It would take like 10 minutes to do this in Houdini but should be very doable in other packages as well although some of the operations might be destructive. There's a lot of 3d modeling tricks that can be utilized to further customize the results too like additional noise, relaxing, localized random subdivisions or chamfering for tighter star clusters etc. Then in Unity you just load the mesh, crop a small subsection of it by random, maybe rotate it too, and then fix or remove any islands that might have been left isolated by the cropping. Having a large enough source mesh ensures that the results will feel random to the player.
|
|
#
?
Apr 15, 2019 08:56
|
|
|
So I'm making a 2D game, and for part of it I want to have one of those cheesy 80s laser grid backgrounds. Easy enough to draw, buuuut I'd like it to be animated programatically. And this is a 2D engine, so I can't just drop in a 3D grid model and call it good. Trying to do something like this, and have the horizontal lines move downwards over time to make it look like the player is moving forward. Drawing horizontal lines further and further downward over time is easy enough, but it doesn't look right since there's no perspective/foreshortening; the lines stay the same distance apart the whole time so it looks wrong. So that's my question: can anyone point me in the right direction regarding figuring out how to spread the lines out as they move downward so they look right? Something simpler than generating a 3D grid at runtime and doing the matrix math myself (no 3D engine underneath)? edit: I feel like the solution involves Pythagoras' theorem somehow, but I just can't seem to put it all together. Can you tell I'm bad at math? Doc Block fucked around with this message at 20:18 on Apr 20, 2019 |
|
#
?
Apr 20, 2019 20:13
|
|
|
Doing simple 3d projections like what you need here is only a few lines of code really so I'd suggest just looking up the math for that E: this is a pretty good tutorial https://github.com/ssloy/tinyrenderer netcat fucked around with this message at 20:46 on Apr 20, 2019 |
|
#
?
Apr 20, 2019 20:43
|
|
|
Thx for the link. I haven't done any 3D math in a long time, so we'll see how long it takes my stupid brain to relearn all this stuff.
|
|
#
?
Apr 20, 2019 21:52
|
|
|
Doc Block posted:So I'm making a 2D game, and for part of it I want to have one of those cheesy 80s laser grid backgrounds. Easy enough to draw, buuuut I'd like it to be animated programatically. And this is a 2D engine, so I can't just drop in a 3D grid model and call it good. Moving the horizontal lines down is the easiest way to go here. You're close in that you want trigonometry, but Pythagoras isn't quite right. You want the inverse tangent (arctan) of camera height/distance. That will give you the angle down from the camera's forward direction. For instance, if you want to have a horizontal grid line every 10 ft and your camera's height off the ground is 6 ft, your first few lines would be: tan-1(6/10) ≈ 30° tan-1(6/20) ≈ 17° tan-1(6/30) ≈ 11° tan-1(6/40) ≈ 9° Now, since you're drawing this on an orthographic camera instead of a perspective camera, you need this to be projected on a flat surface. Easy to do - just use trig again. This time we're going to use tangent because we're going from an angle to a scalar ratio. tan(30°) gives you ≈ 0.58, which is your opposite over adjacent (height over distance). We have a fixed distance to the projected surface, (you'll have to play around with it to get the right scale, but let's call it 10), so you just multiply by that distance to give you your height (5.8 of whatever units you're working in). This is distance below the horizon, remember. Now wait, tan and arctan are inverses of each other, so taking the tangent of the inverse tangent just gives you the same thing you started with, and you can simplify to just the following: lineOffset = cameraHeight / (i * lineDistance) * cameraDistance I wrote a quick program in C# to show the concept. code: Hope this helps! KillHour fucked around with this message at 00:00 on Apr 21, 2019 |
|
#
?
Apr 20, 2019 23:56
|
|
|
KillHour posted:Moving the horizontal lines down is the easiest way to go here. You're close in that you want trigonometry, but Pythagoras isn't quite right. You want the inverse tangent (arctan) of camera height/distance. That will give you the angle down from the camera's forward direction. Yes, this is exactly what I needed. Thank you!  
|
|
#
?
Apr 21, 2019 01:53
|
|
|
Doc Block posted:Yes, this is exactly what I needed. Thank you! Nice! If you want to make it more retro, you could try to get rid of the mush of very closely-spaced lines near the horizon. I think something like "fixed horizon line, draw 7 mobile lines starting from the bottom" would probably do the trick.
|
|
#
?
Apr 21, 2019 02:00
|
|
|
Yeah it needs some sort of GUI with a bunch of sliders so I can dial in juuuust the right look and then use it in the actual game.
|
|
#
?
Apr 21, 2019 02:16
|
|
|
TooMuchAbstraction posted:Nice! If you want to make it more retro, you could try to get rid of the mush of very closely-spaced lines near the horizon. I think something like "fixed horizon line, draw 7 mobile lines starting from the bottom" would probably do the trick.
|
|
#
?
Apr 21, 2019 02:36
|
|
|
roomforthetuna posted:Another option (either in addition or instead) would be to make the lines' brightness a bit darker by distance (as a proxy for the lines getting thinner as they get further away, which they would in reality). You might also want to make them thicker when they get close! I would go with this. It's easy to add, because you can use the same math to figure out how that should fall off. Looks great, though!
|
|
#
?
Apr 21, 2019 03:11
|
|
|
Been tinkering around with my Galaxy generator some more. All the awesome advice I received previously was a little too tedious and advanced for me, so I adopted a very "unity" solution and just cast rays from each star to search for neighbors to make connections with. It's actually faster than what I was doing before, and the results are almost exactly what I'm after . There are still a few intersecting hyperlanes but it's much more readable. Sometime's it will generate little pockets of isolated stars, and that's very much intentional.
|
|
#
?
Apr 21, 2019 17:32
|
|
|
Kibbles n Shits posted:Been tinkering around with my Galaxy generator some more. All the awesome advice I received previously was a little too tedious and advanced for me, so I adopted a very "unity" solution and just cast rays from each star to search for neighbors to make connections with. It's actually faster than what I was doing before, and the results are almost exactly what I'm after . If you're happy with a "unity" solution, and if you still want some performance improvement, you might want to go with some sort of sphere/circle collision in an area around each star, rather than raycasting, since that way you'll get all the nearby neighbors in one pass rather than presumably having to take many shots to find something with raycasting. Edit: Physics.OverlapSphere or Physics2D.OverlapCircleAll.
|
|
#
?
Apr 21, 2019 18:06
|
|
|
Well the example I posted above is the largest galaxy size I've decided on and it took around 2 seconds to generate in the Unity editor so I'm not too worried about it, if it gets me what I want. I was using spherical collision before and I like the way this looks a lot more. I thought some sort of Planar graph would be best and I understand it on a conceptual level but I was spinning my wheels with the actual implementation. I just do this on occasion as a hobby. Edit: I only cast 8 rays (at most) from each star, I don't repeat it indefinitely until a neighbor is found. Kibbles n Shits fucked around with this message at 18:23 on Apr 21, 2019 |
|
#
?
Apr 21, 2019 18:17
|
|
|
People were mentioning specific algorithms like Delauney triangulation, but the general term you were looking for was Planar Graph, which is a graph in which no edges intersect. Granted, searching "generate planar graph" is just going to get you Delauney triangulation or Voronoi diagrams so...  Technically there is a technique called Planarization which has a step that involves finding the largest planar subgraph (the biggest set of nodes and edges which do not intersect, which is what you asked for) but it's... uh... NP-hard, though there are approximations available. However, if/once you know a graph is planar for sure (which can be checked in O(|V|), that is, it can be drawn with no intersections, see the Wikipedia article for an algorithm), there's an O(|V|) algorithm for computing a proper straight line layout (called an embedding). Doing what you're doing now works just fine and probably creates more interesting (i.e. not triangle shaped) graphs, though. Linear Zoetrope fucked around with this message at 10:05 on Apr 23, 2019 |
|
#
?
Apr 23, 2019 10:02
|
|
|
Doc Block posted:Yes, this is exactly what I needed. Thank you! Nice job, this looks rad!
|
|
#
?
Apr 23, 2019 12:02
|
|
|
Are fur shaders available or even do-able in unity on an iphone6(s)?
|
|
#
?
Apr 23, 2019 19:17
|
|
|
To the fellow making the starmap: One really easy optimisation for that kind of system is to have a grid, say 20x20, so that each star is placed in one cell. Now when you need to do some intersection, etc. calculations, you probably know that only the stars within the current star's grid coordinates +/- 4 grid units need to be taken into account. Back when I was learning programming, I did a simple physics engine using this kind of pattern and it was able to handle an enormous number of objects whose physics were calculated 300 times a second. https://www.youtube.com/watch?v=dMamNqJ3-XU (yeah 240p like it's the 90s, but my PC couldn't handle recording too well back in the day) The source is here: https://github.com/SnowblindFatal/Glomes SnowblindFatal fucked around with this message at 13:13 on Apr 26, 2019 |
|
#
?
Apr 26, 2019 13:07
|
|
|
Shaocaholica posted:Are fur shaders available or even do-able in unity on an iphone6(s)? Anything is possible on any platform, the questions are how well can you do it, how fast can you draw it and what balance do you need between the two? E:For a more thorough answer, whatever you're thinking probably isn't doable in terms of performance and stuff. Like you don't have tesselation shaders and the power isn't there to do GOOD looking fur in an interactive time. Joda fucked around with this message at 14:42 on May 2, 2019 |
|
#
?
May 2, 2019 14:38
|
|
|
Hello friends Because I'm a masochist, I'd like to program a DOS game, directly on the VGA hardware, either mode 13 or mode-X I know C and C++ very well, but I've only ever learnt their standard libraries and and modern libraries like SDL and SFML and never did things on the "metal" like bios interrupts, dos.h and mem.h from the cool old days of DOS programming I have access to a real DOS PC with 6.22 and Windows 3.1, also DOSBox, various Borland and MS compilers from the late 80's and early 90's - what's the best original compiler? I looked into DJGPP but I probably want real mode not protected mode? Can anyone recommend some good books from back in the day? Covering things like the DOS API/Interrupts, VGA hardware, Borland/MS C, maybe some Turbo Assembler/Microsoft Assembler? I feel like things like the oft recommended Mike Abrash books are for people who already know the basics of DOS and VGA programming and I'd need to start simpler Thank you
|
|
#
?
May 7, 2019 22:53
|
|
|
c0burn posted:Hello friends Review Fabian sanglards’s book on wolf3d It’s new, but goes into good detail.
|
|
#
?
May 7, 2019 23:21
|
|
|
c0burn posted:Hello friends
|
|
#
?
May 10, 2019 22:39
|
|
|
c0burn posted:Hello friends Please post updates in this thread or elsewhere because this sounds rad!
|
|
#
?
May 11, 2019 15:32
|
|
|
c0burn posted:Hello friends If you've been googling you might have found this but there's a tutorial series online that might help: http://www3.telus.net/alexander_russell/course/introduction.htm
|
|
#
?
May 11, 2019 17:34
|
|
|
So I have this mesh generated from points on a grid. It's relatively flat and simple compared to the number of vertices it has. I'm trying to build a mesh collider without so many faces. As you can imagine it can be a lot simpler. I basically have vertices at every point on the grid but I can probably span some triangles out over much wider distances and save on a whole bunch of collision computation. Am having trouble figuring out what algorithms there are for performing that optimisation. 
Nolgthorn fucked around with this message at 23:03 on May 19, 2019 |
|
#
?
May 19, 2019 22:58
|
|
|
3D convex hull? Or if you don't need it very precise just take the most extreme points in each axis and fit a capsule or cuboid collider.
|
|
#
?
May 19, 2019 23:13
|
|
|
What's really cool is that I've switched to godot game engine and it seems to have what you mentioned built in. It's just not documented well, as you would expect. All I might have to do is figure out how to organise my nodes so that it's happy I may not need to worry about it.
|
|
#
?
May 20, 2019 00:35
|
|
|
At first glance I thought you were looking for a player/enemy object collider but looking again I think maybe it's for terrain instead? In that case maybe what I suggested isn't going to be precise enough. Godot does have some nice inbuilt meshing tools for objects that you just instance and use as is. But I did find that if you want to do procedural terrain you're maybe better off rolling your own vertex handling and only constructing the finished mesh "in engine" for rendering, pathfinding and collision. For one example I couldn't figure out how to allow shared vertices between triangles with SurfaceTool and MeshDataTool so mesh deformation was much more expensive than it needed to be. Also when I ended up wanting my vertices or triangles to be associated with additional properties beyond position, normals and colour I was having to build another data structure in parallel with the mesh anyway, so it made sense to me to combine the two (also potentially lets you offload the heavy lifting to a C++ library with GDNative). As you say, the documentation is a bit spotty in this area so it could be that I'm just dumb and there's a better way.
|
|
#
?
May 20, 2019 00:53
|
|
|
|
| # ? May 11, 2024 16:19 |
|
|
Sounds like a perfect use-case for using GPU tesselation. Use a rougher mesh as the source for the collision and rendering mesh, then have the GPU split up the vertices and do a bit of deformation based on a bump-map. Could be that Godot just does that for you behind the scenes, not really familiar with it.
|
|
#
?
May 20, 2019 00:57
|
|
